带时间窗的三维装载物流配送优化方法研究

针对城市物流配送优化研究在客户服务时间窗和货物装载方式合理结合方面存在的不足,考虑物流配送车厢货物装载方式与客户访问序列相关的特征对车厢空间进行合理的区域划分。首先,构建了包含配送中心的固定成本、配送车辆的运输成本、维修成本、租赁成本和违反时间窗惩罚成本的物流运营成本最小化和配送车辆空间利用率最大化的双目标优化模型;然后,提出一种结合遗传算法(GA)全局搜索能力和禁忌搜索算法(TS)局部搜索能力的GA-TS混合算法求解模型;最后,结合重庆市某配送中心的三维装载物流配送实例数据进行了优化计算,实验结果给出了带时间窗的三维装载物流配送路径优化方案,并进行了不同车厢空间分区模式下平均装载率、物流运营成本和车辆使用数的比较分析。研究表明,当客户需求货物种类数与车辆的空间区域划分数相等且按货物类型进行区域划分时,物流运营成本最小,配送车辆使用数最少和车辆平均装载率最高。     

一种登陆作战兵力上船装载方案优化计算方法

建立登陆作战兵力上船装载方案优化模型,针对大规模登陆作战兵力上船装载方案确定问题特点,提出一种用需装载兵力、可用舰船和可用泊位类型排列表示方案的方案编码方法,称为方案的类型排列基因码.给出排列基因码生成及进化方法,实现装载方案的遗传优化.计算结果表明,使用该方法可以在较短时间内得到较好的上船装载方案.     

多点收缩混沌优化方法及全局收敛性证明

针对目前混沌优化算法在选取局部搜索空间时的盲目性,提出一种具有自适应调节局部搜索空间能力的多点收缩混沌优化方法.该方法在当前搜索空间搜索时保留多个较好搜索点,之后利用这些点来确定之后的局部搜索空间,以达到对不同的函数和当前搜索空间内已进行搜索次数的自适应效果.给出了该算法以概率1收敛的证明.仿真结果表明该算法有效的提高了混沌优化算法的性能,改善了混沌算法的实用性.     

面向电商终端物流配送的电动车配置与路径集成优化

在电子商务终端物流配送方面,存在能力与需求的矛盾。一方面,电动车存在货物容量约束和电池电量约束,配送能力有限;另一方面,一个物流配送点需要为众多的消费者进行门到门的配送,配送任务繁重。针对电子商务环境下终端物流配送规模大、电动车货物容量和行驶里程有限的问题,建立电商终端物流配送的电动车配置与路径规划集成优化模型,并提出一种基于临近城市列表的双策略蚁群算法,实现物流配送电动车辆配置与配送路径集成优化。该模型以电动车辆数最少和总路径最短为目标,以电动车货物容量和电池续航里程为约束,是带容量的车辆路径问题的进一步扩展,属于双容量约束路径规划问题。双策略蚁群算法在货物容量和续航里程的约束下,将蚁群搜索策略分为两类,即基于临近城市列表的局部搜索策略和全局搜索策略,在提高搜索效率的同时防止陷入局部优化。最后,通过阿里巴巴旗下菜鸟网络科技有限公司在上海的30组真实配送数据进行了测试,验证双策略蚁群算法显著优于一般蚁群算法。     

组合优化算法中摆脱局部极小值的几种策略

局部搜索算法是一种非常有效的求解组合优化问题的算法 ,它具有通用、灵活等特点 .但是 ,由于搜索空间和目标函数的复杂性 ,目标函数在搜索空间中有许多局部极小值点 ,使算法在这些局部极小值点处被“卡住”,大大影响算法的效果 .对于此问题 ,笔者查阅了大量文献资料 ,结合自己的研究实践 ,总结出几种跳出局部极小“陷井”的策略 .使用这些策略 ,有望使算法更加完善 ,在求解组合优化问题过程中更能发挥其作用 .     

组合优化算法中摆脱局部极小值的几种策略

局部搜索算法是一种非常有效的求解组合优化问题的算法,它具有通用、灵活等特点。但是,由于搜索空间和目标函数的复杂性,目标函数在搜索空间中有许多局部极小值点,使算法在这些局部极小值点处被“卡住”,大大影响算法的效果。对于此问题,笔查阅了大量献资料,结合自己的研究实践,总结出几种跳出局部极小“陷井”的策略,使用这些策略,有望使算法更加完善,在求解组合优化问题过程中更能发挥其作用。     

成品油配送多车舱车辆指派及路径优化问题研究

针对成品油配送中多车型、多车舱的车辆优化调度难题,综合考虑多车型车辆指派、多车舱车辆装载及路径安排等决策,以派车成本与油耗成本之和的总成本最小为目标,建立了多车型多车舱的车辆优化调度模型。为降低模型求解的复杂性,本文提出一种基于C-W节约算法的“需求拆分→合并装载”的车辆装载策略,并综合利用Relocate和Exchange算子进行并行邻域搜索改进,获得优化的成品油配送方案。最后,通过算例验证了本文提出的模型与算法用于求解大规模成品油配送问题的有效性。并通过数据实验揭示了以下规律:1)多车舱车辆相对于单车舱车辆在运营成本上具有优越性;2)大型车辆适合远距离配送,小型车辆适合近距离配送;3)多车型车辆混合配送相对于单车型车辆配送在运营成本上具有优越性。这些规律可为成品油配送公司的车辆配置提供决策参考。     

0-1背包问题的蜂群优化算法

在项目决策与规划、资源分配、货物装载、预算控制等工作中,提出了0-1背包问题.0-1背包问题是组合优化中的典型NP难题,根据群集智能原理,给出一种基于蜂群寻优思想的新算法—蜂群算法,并针对0-1背包问题进行求解.经实验仿真并与蚁群算法计算结果作对比,验证了算法在0-1背包问题求解上的有效性和更快的收敛速度.     

乘用车物流运输装载模型研究

对乘用车物流运输计划问题进行了研究,首先,建立了以单辆轿运车实载率最大为目标的单车最佳装载方案模型,以该方案配送乘用车辆直到运输任务完成以获得初始轿运车数,其次以空载率最小为目标设计了数量调整模型对初始轿运车数进行优化,得到最优装载方案模型.基于上述优化模型计算最小的轿运车数,建立在轿运车数量限制下的最短行驶里程模型,选择总行驶里程最小的装载方案作为最优的配送方案.最后建立基于路径的物流运输装载模型,运用Floyd算法计算任意起讫点间的最短路径,设计了一种全局搜索算法得到一种合理的配送方案,并以空载率最小为目标对方案进行优化.     

一类非光滑凸优化问题的邻近梯度算法

考虑求解目标函数为光滑损失函数与非光滑正则函数之和的凸优化问题的一种基于线搜索的邻近梯度算法及其收敛性分析,证明了在梯度局部Lipschitz连续条件下该算法是R-线性收敛的,并在非光滑部分为稀疏块LASSO正则函数情况下给出了误差界条件成立的证明,得到了线性收敛率.最后,数值实验结果验证了方法的有效性.     

Genetic algorithm with automatic termination and search space rotation

In the last two decades, numerous evolutionary algorithms (EAs) have been developed for solving optimization problems. However, only a few works have focused on the question of the termination criteria. Indeed, EAs still need termination criteria prespecified by the user. In this paper, we develop a genetic algorithm (GA) with automatic termination and acceleration elements which allow the search to end without resort to predefined conditions. We call this algorithm “Genetic Algorithm with Automatic Termination and Search Space Rotation”, abbreviated as GATR. This algorithm utilizes the so-called “Gene Matrix” (GM) to equip the search process with a self-check in order to judge how much exploration has been performed, while maintaining the population diversity. The algorithm also implements a mutation operator called “mutagenesis” to achieve more efficient and faster exploration and exploitation processes. Moreover, GATR fully exploits the structure of the GM by calling a novel search space decomposition mechanism combined with a search space rotation procedure. As a result, the search operates strictly within two-dimensional subspaces irrespective of the dimension of the original problem. The computational experiments and comparisons with some state-of-the-art EAs demonstrate the effectiveness of the automatic termination criteria and the space decomposition mechanism of GATR.     

MDTri: robust and efficient global mixed integer search of spaces of multiple ternary alloys

Computational materials design has suffered from a lack of algorithms formulated in terms of experimentally accessible variables. Here we formulate the problem of (ternary) alloy optimization at the level of choice of atoms and their composition that is normal for synthesists. Mathematically, this is a mixed integer problem where a candidate solution consists of a choice of three elements, and how much of each of them to use. This space has the natural structure of a set of equilateral triangles. We solve this problem by introducing a novel version of the DIRECT algorithm that (1) operates on equilateral triangles instead of rectangles and (2) works across multiple triangles. We demonstrate on a test case that the algorithm is both robust and efficient. Finally, we offer an explanation of the efficacy of DIRECT—specifically, its balance of global and local search—by showing that “potentially optimal rectangles” of the original algorithm are akin to the Pareto front of the “multi-component optimization” of global and local search.     

A tree search method for the container loading problem with shipment priority

This paper addresses a special kind of container loading problem with shipment priority. We present a tree search method, which is based on a greedy heuristic. In the greedy heuristic, blocks made up of identical items with the same orientation are selected for packing into a container. Five evaluation functions are proposed for block selection, and the different blocks selected by each evaluation function constitute the branches of the search tree. A method of space splitting and merging is also embedded in the algorithm to facilitate efficient use of the container space. In addition, the proposed algorithm covers an important constraint called shipment priority to solve practical problems. The validity of the proposed algorithm is examined by comparing the present results with those of published algorithms using the same data.     

Learning gradients via an early stopping gradient descent method

We propose an early stopping algorithm for learning gradients. The motivation is to choose “useful” or “relevant” variables by a ranking method according to norms of partial derivatives in some function spaces. In the algorithm, we used an early stopping technique, instead of the classical Tikhonov regularization, to avoid over-fitting.After stating dimension-dependent learning rates valid for any dimension of the input space, we present a novel error bound when the dimension is large. Our novelty is the independence of power index of the learning rates on the dimension of the input space.     

A modified quasisecant method for global optimization

This paper presents an algorithm for global optimization problem whose objective functions is Lipschitz continuous but not necessarily differentiable. The proposed algorithm consists of local and global search procedures which are based on and inspired by quasisecant method, respectively. The aim of the global search procedure is to identify “promising” basins in the search space. Once a promising basin is identified, the search procedure skips from an exhausted area to the obtained basin, and the local search procedure is then applied at this basin. It proves that the proposed algorithm converges to the global minimum solution if the local ones are finite and isolated. The proposed method is tested by academic benchmarks, numerical performance and comparison show that it is efficient and robust. Finally, The method is applied to solve the sensor localization problem.     

Port space allocation with a time dimension

In the Port of Singapore, as in many other ports, space has to be allocated in yards for inbound and transit cargo. Requests for container space occur at different times during the planning period, and are made for different quantities and sizes of containers. In this paper, we study space allocation under these conditions. We reduce the problem to a two-dimensional packing problem with a time dimension. Since the problem is NP-hard, we develop heuristic algorithms, using tabu search, simulated annealing, a genetic algorithm and ‘squeaky wheel’ optimization, as solution approaches. Extensive computational experiments compare the algorithms, which are shown to be effective for the problem.     

A hybrid method combining continuous tabu search and Nelder–Mead simplex algorithms for the global optimization of multiminima functions

Tabu search (TS) is a metaheuristic, which proved efficient to solve various combinatorial optimization problems. However, few works deal with its application to the global minimization of functions depending on continuous variables. To perform this task, we propose an hybrid method combining tabu search and simplex search (SS). TS allows to cover widely the solution space, to stimulate the search towards solutions far from the current solution, and to avoid the risk of trapping into a local minimum. SS is used to accelerate the convergence towards a minimum. The Nelder–Mead simplex algorithm is a classical very powerful local descent algorithm, making no use of the objective function derivatives. A “simplex” is a geometrical figure consisting, in n-dimensions, of (n+1) points. If any point of a simplex is taken as the origin, the n other points define vector directions that span the n-dimension vector space. Through a sequence of elementary geometric transformations (reflection, contraction and extension), the initial simplex moves, expands or contracts. To select the appropriate transformation, the method only uses the values of the function to be optimized at the vertices of the simplex considered. After each transformation, the current worst vertex is replaced by a better one. Our algorithm called continuous tabu simplex search (CTSS) implemented in two different forms (CTSS_single, CTSS_multiple) is made up of two steps: first, an adaptation of TS to continuous optimization problems, allowing to localize a “promising area”; then, intensification within this promising area, involving SS. The efficiency of CTSS is extensively tested by using analytical test functions of which global and local minima are known. A comparison is proposed with several variants of tabu search, genetic algorithms and simulated annealing. CTSS is applied to the design of a eddy current sensor aimed at non-destructive control.