基于时空聚类求解带容积约束的选址-路径问题

选址-路径问题是供应链管理和物流系统规划中的一个重要问题,对总成本具有十分重要的影响.对考虑配送中心容积约束的带时间窗的选址-路径问题进行研究,建立以总成本最小和客户满意度最大为目标的多目标规划模型,提出两阶段算法对其进行求解.首先,利用k-means聚类算法确定配送中心选址;然后,提出一种基于时间-空间双因素的客户划分方法以确定配送中心所服务客户;最后,利用粒子群算法对各配送中心的配送路径进行规划.数值算例表明,所提出的算法较其他已有算法,均能有效地降低物流运作总成本及总配送路径长度,为解决带容积约束及时间窗的选址-路径问题提供了一种新的解决思路.     

两阶段组合优化算法的农产品物流配送中心选址研究

提出两阶段组合优化算法的农产品物流配送中心选址算法。以农产品物流配送中心选址假设为基础,采用基于聚集度的启发式算法划分客户类别,确定备选配送中心的配送界限;以配送服务的可靠性最大化为目标,以配送总成本为约束条件,建立农产品物流配送中心选址的优化模型,使用免疫算法求解优化模型。实验结果表明,算法可有效获取最佳农产品物流配送中心选址,所选取配送中心到各配送点的运输费用较低,到达各个配送点的运输距离均未超过600元/吨;所选取配送中心到各个配送点的距离最小。     

4PL路径优化问题0-1规划模型与求解

研究带有时间窗的第四方物流(fourth-party logistics,4PL)路径优化问题,在满足客户对配送时间要求的同时实现物流运输成本最小,以提供最优的配送方案.根据问题本身的特点,建立了带有时间窗的4PL路径优化问题的0-1整数规划模型,采用CPLEX软件分别求解了7节点、15节点和30节点的算例.将算例结果与基于路进行建模的和声搜索算法和枚举算法进行了对比,结果表明CPLEX可以为带有时间窗的4PL路径优化问题提供最优的解决方案,验证了模型的有效性.     

基于情景分析的军事物流配送中心选址模型

研究不确定战时情景下的军事物流配送中心选址问题。兼顾军事物流系统性能优化和成本节约建立了两个随机规划模型,模型中引入情景分析,考虑了设施损毁、库容和配送时间约束。讨论了模型求解方法,通过求解模型得到配送中心选址、选型和预置量决策。模型一在情景出现前为每个用户指派了首选与后备供应点,模型二给出了每个情景下的配送方案。仿真算例表明了模型的合理性和解法的有效性,也验证了模型一优于模型二。     

基于粒子群算法的满载需求可拆分车辆路径规划

为了更加合理地规划车辆配送路径,尽可能使用最少的车辆数和最短路径长度来完成整个客户点的配送任务,提出一种基于粒子群算法的满载需求可拆分车辆路径(F-SDVRP)规划策略,在配送过程中通过确保任何一辆满载的配送车辆从配送点出发后均以“最优”的配送路径进行配送来达到配送的总路径“最优”要求,并通过粒子群算法不断优化整个客户点的配送顺序.仿真结果表明,在求解相关客户点配送问题时,所提出的车辆规划策略得到的结果优于对比文献中的求解方法,在配送车辆数相同的情况下,最大的路径长度减少率达到8.21%.此外,各算例的仿真结果表明,所提出的策略的寻优结果稳定,粒子群算法可以解决满载需求可拆分车辆路径规划问题.     

新零售下生鲜产品闭环物流网络模糊规划

针对我国新零售模式的快速发展，消费者对生鲜产品需求与退货的模糊不确定性问题，考虑最低物流总成本、最佳设施选址以及最优配送车辆运输路径的决策，构建了新零售下生鲜产品闭环物流网络模糊规划模型。为求解该模型，将需求量与退货量看成三角模糊参数，利用模糊机会约束方法将模糊约束转化为等价的清晰条件。以上海市某生鲜电商企业为实例，通过置信水平的敏感性分析以及遗传算法与粒子群算法的双求解，验证了模型的有效性与可行性，进而为相关决策者提供了借鉴。     

需求可拆分车辆路径问题的禁忌搜索算法

为解决实际配送运输中的车辆路径问题（Vehicle Routing Problem,VRP）,通过改进传统的数学模型,解除每个客户需求只能由l辆车配送的约束,建立改进的可拆分车辆路径问题（Split Delivery VRP,SDVRP）数学模型,并利用禁忌搜索算法（Taboo Search Algorithm,TSA）进行求解．在TSA的设计中,根据SDVRP模型的特点对初始解、邻域搜索和解的评价等进行特殊处理．算例表明,该模型不仅可以解决VRP模型中不允许配送点需求量超出装载量的限制,而且通过相应配送点需求量的拆分和重新组合,可节省车辆数目、缩短路线长度、提高车辆装载率．     

应急物流的分批配送规划及蚁群优化求解

针对应急物流的特点,建立分批配送车辆路径规划（SDVRP）模型,实现三大目标：（1）未满足需求最少化;（2）总配送时间最短化;（3）各灾点失衡度最低化。以加权求和的方式转化为单一优化目标,分批配送也节约了救援路径数/车辆数。借鉴并改进最大-最小蚁群算法,设定信息素增量的上下限,避免了结果陷入局部最优。给出数值算例,验证了模型和算法的有效性。     

基于新鲜度的冷链物流配送多目标优化模型*

针对传统选址模型忽视客户对物流服务水平满意程度这方面的不足,建立考虑客户满意度的基于新鲜度对损失成本影响的冷链配送中心选址模型。本文以客户满意度来表示物流的服务质量并结合易腐品的新鲜度对时间的敏感性特征,建立了最小化物流成本和最大化客户满意度的多目标优化模型,采用主要目标法将模型转化成单目标模型进行求解。求解算例所得的多组非劣解反映了物流成本与客户满意度之间的悖反关系,同时包含了以物流成本最小化为目标的传统选址模型的最优解,表明了多目标模型的优越性。对比结果说明新鲜度条件下建立的冷链物流配送网络模型比传统模型节省了更多的物流成本,进而验证了该模型的正确性。     

大型物流车辆配送线路自适应调度方法

为了有效提高物流配送车辆的利用率,降低配送车辆的空载率及物流运输成本,需要对大型物流车辆配送线路自适应调度方法进行研究。当前方法多是采用通过对物流车辆配送过程中的调度与路径选择进行分析,建立多类型的物流配送车辆调度模型,并构建改进后的遗传算法,对物流调度模型的算法效率以及计算时间和复杂度进行优化,以获取物流车辆配送调度问题的最优解,但该方法存在过程较为繁琐的问题。为此,提出一种大型物流车辆配送线路自适应调度方法。该方法首先建立物流车辆配送线路调度问题的数学模型,为实现自适应调度方法对数学模型进行优化求出最优解,利用蚁群算法对物流车辆配送调度数学模型的最优解进行优化,获取最优路径的适应度初始化蚁群算法的各客户点之间的信息素,从而得出了优化的最优路径;以优化的最优路径完成对大型物流车辆配送线路自适应调度。仿真实验表明,利用蚁群算法不仅加快了物流配送路线调度优化问题求解的速度,降低了物流运输的成本,而且获取了最优解的概率,比其他调度算法具有更明显的优势。     

Lower and upper bounds for the two-echelon capacitated location-routing problem

In this paper, we introduce two algorithms to address the two-echelon capacitated location-routing problem (2E-CLRP). We introduce a branch-and-cut algorithm based on the solution of a new two-index vehicle-flow formulation, which is strengthened with several families of valid inequalities. We also propose an adaptive large-neighbourhood search (ALNS) meta-heuristic with the objective of finding good-quality solutions quickly. The computational results on a large set of instances from the literature show that the ALNS outperforms existing heuristics. Furthermore, the branch-and-cut method provides tight lower bounds and is able to solve small- and medium-size instances to optimality within reasonable computing times.     

行驶时间和服务时间随机的集配货一体的分批配送车辆路径优化

将铁路物流中心集配货路径问题抽象为行驶时间和服务时间随机的集送货一体的分批配送车辆路径问题进行优化.根据问题特点建立带修正的随机规划模型,对迭代局部搜索算法进行改进,设计允许分批配送的初始解构造算法、局部搜索算法和扰动机制.算例测试证实:分批配送在中等规模和大规模算例中能发挥较好的作用,大部分中等规模和大规模算例都比不允许分批配送时所得到的解更优,部分中等规模和大规模算例车辆数有所减少;配送点数随着算例规模的扩大而增加,但是配送点数占顾客点数的比例却逐步降低;随机因素随机性增加将导致目标函数增大,对分批配送点数的影响不大.     

双层车辆路径问题的混合启发式算法

针对与城市物流密切相关的双层车辆路径问题(2E-VRP),提出了一种用来求解的混合启发式算法.该算法利用贪心算法的快速性、蚁群算法的搜索多样性以及邻域搜索算法较强的局部寻优能力来提高求解质量,加速算法的收敛性.把该算法应用于22个测试算例和3个大规模的算例,并与同类研究进行了比较.实验结果表明,混合启发式算法不仅能保证较高的精确性,而且具有很高的效率;与精确性最高的同类算法相比,虽然在解的质量方面稍逊,但在求解速度方面表现出了明显的优势.实验结果还显示了构建双层城市物流系统的潜在收益,中转站的设置能够在一定条件下显著提高城市物流效率.     

Cooperation and profit allocation in two-echelon logistics joint distribution network optimization

Collaborative two-echelon logistics joint distribution network can be organized through a negotiation process via logistics service providers or participants existing in the logistics system, which can effectively reduce the crisscross transportation phenomenon and improve the efficiency of the urban freight transportation system. This study establishes a linear optimization model to minimize the total cost of two-echelon logistics joint distribution network. An improved ant colony optimization algorithm integrated with genetic algorithm is presented to serve customer clustering units and resolve the model formulation by assigning logistics facilities. A two-dimensional colony encoding method is adopted to generate the initial ant colonies. Improved ant colony optimization combines the merits of ant colony optimization algorithm and genetic algorithm with both global and local search capabilities. Finally, an improved Shapley value model based on cooperative game theory and a cooperative mechanism strategy are presented to obtain the optimal profit allocation scheme and sequential coalitions respectively in two-echelon logistics joint distribution network. An empirical study in Guiyang City, China, reveals that the improved ant colony optimization algorithm is superior to the other three methods in terms of the total cost. The improved Shapley value model and monotonic path selection strategy are applied to calculate the best sequential coalition selection strategy. The proposed cooperation and profit allocation approaches provide an effective paradigm for logistics companies to share benefit, achieve win–win situations through the horizontal cooperation, and improve the negotiation power for logistics network optimization.     

Parallel island based Memetic Algorithm with Lin–Kernighan local search for a real-life Two-Echelon Heterogeneous Vehicle Routing Problem based on Brazilian wholesale companies

This paper deals with a Two-Echelon Fixed Fleet Heterogeneous Vehicle Routing Problem (2E-HVRP) faced by Brazilian wholesale companies. Vehicle routing problems with more than one phase are known as Multi-Echelon VRP and consider situations in which freight is moved through some intermediate facilities (e.g., cross-docks or distribution centers) before reaching its destination. The first phase of the problem dealt here is to choose a first-level vehicle, from an heterogeneous set, that will leave a depot and reach an intermediate uncapacitated facility (satellite) to serve a set of second-level vehicles. After that, it is necessary to define routes for smaller vehicles, also from an heterogeneous set, that will visit a set of customers departing from and returning to a satellite. The solution proposed here is an efficient island based memetic algorithm with a local search procedure based on Lin–Kernighan heuristic (IBMA-LK). In order to attest the algorithm’s efficiency, first it was tested in single echelon HVRP benchmark instances. After that the instances were adapted for two-echelon context and used for 2E-HVRP validation and, finally, it was tested on 2E-HVRP instances created using real world normalized data. Localsolver tool was also executed for comparison purposes. Promising results (which corroborate results obtained on the real problem) and future works are presented and discussed.     

基于场景动态度的两级配送路径问题

针对城市配送过程中出现的交通限行和需求不确定性等问题,将配送周期划分为初始配送阶段和动态补货阶段,路径中包含枢纽型物流中心、配送型物流中心和客户,研究其共同构成的两级车辆配送路径优化问题.考虑到问题的动态性,提出前摄性需求配额策略及响应性补货策略,构建基于场景动态度的两级动态车辆路径问题数学模型.设计融合扫描算子的禁忌搜索算法,完成车辆初始阶段的配送路径优化;根据场景动态度,设计修复/更新性动态客户的响应策略,快速响应动态需求.最后,通过仿真算例验证模型和算法的有效性,实验结果表明,所提出的设计策略能够有效降低动态客户对低动态度应用场景初始路径的干扰,并简化高动态度场景下的路径优化复杂度.     

An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem

In this paper, an enhanced ant colony optimization (EACO) is proposed for capacitated vehicle routing problem. The capacitated vehicle routing problem is to service customers with known demands by a homogeneous fleet of fixed capacity vehicles starting from a depot. It plays a major role in the field of logistics and belongs to NP-hard problems. Therefore, it is difficult to solve the capacitated vehicle routing problem directly when solutions increase exponentially with the number of serviced customers. The framework of this paper is to develop an enhanced ant colony optimization for the capacitated vehicle routing problem. It takes the advantages of simulated annealing and ant colony optimization for solving the capacitated vehicle routing problem. In the proposed algorithm, simulated annealing provides a good initial solution for ant colony optimization. Furthermore, an information gain based ant colony optimization is used to ameliorate the search performance. Computational results show that the proposed algorithm is superior to original ant colony optimization and simulated annealing separately reported on fourteen small-scale instances and twenty large-scale instances.     

基于层次遗传算法的物流配送中心选址策略*

在考虑物流规划部门和客户双方利益的基础上,采用双层规划模型描述物流配送中心的选址问题。基于进化博弈与多目标优化的思想设计了层次遗传算法来求解该模型,通过两个遗传算法的交互迭代求解物流配送中心选址问题。最后通过算例验证了模型与算法的可行性。     

一种求解两级车辆路径问题的Memetic 算法

两级车辆路径问题是指物资必须先由中心仓库配送至中转站(第1级),再由中转站配送至客户(第2级)的一种车辆路径问题。针对该NP难问题提出一种Memetic算法通过自底向上的方式进行求解。首先利用改进的最优切割算法MDVRP-Split将客户合理分配至中转站;然后采用局部搜索解决第1级问题,交叉产生的精英个体通过局部搜索改进。标准算例的测试结果表明,所提出算法更注重求解质量与求解效率的平衡,性能优于其他现有的两种算法。     

A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem

The two-echelon location-routing problem (LRP-2E) is raised by the design of transportation networks with two types of trips: first-level trips serving from one main depot a set of satellite depots, to be located, and second-level trips supplying customers from these satellites. In the proposed multi-start iterated local search (MS-ILS), three greedy randomized heuristics are used cyclically to get initial solutions. Each ILS run alternates between two search spaces: LRP-2E solutions, and travelling salesman (TSP) tours covering the main depot and the customers. The number of iterations allotted to a run is reduced whenever a known solution (stored in a tabu list) is revisited. MS-ILS can be reinforced by a path-relinking procedure (PR), used internally for intensification, as post-optimization, or both. On two sets with 24 and 30 LRP-2E instances, MS-ILS outperforms on average two GRASP algorithms and adding PR brings a further improvement. Our metaheuristic also surpasses a tabu search on 30 instances for a more general problem with several main depots. It is still effective on a particular case, the capacitated location-routing problem (CLRP): In a comparison with four published metaheuristics, only one (LRGTS, Prins et al., 2007) does better.