多时间窗车辆路径问题的智能水滴算法

研究了多时间窗车辆路径问题,考虑了车容量、多个硬时间窗限制等约束条件,以动用车辆的固定成本和车辆运行成本之和最小为目标,建立了整数线性规划模型。根据智能水滴算法的基本原理,设计了求解多时间窗车辆路径问题的快速算法,利用具体实例进行了模拟计算,并与遗传算法的计算结果进行了对比分析,结果显示,利用智能水滴算法求解多时间窗车辆路径问题,能够以很高的概率得到全局最优解,是求解多时间窗车辆路径问题的有效算法。     

集中通勤接送服务的最小化成本模型及算法

本文针对集中通勤接送服务业务流程中的车次分配与调度问题,建立了以最小化成本为目标的0-1混合整数规划模型,刻画了该问题所具有的多目标抵达地、多车协作、多行程车次等特征事实,同时考虑顾客满意度,以获得不同满意度下的近似最小成本。根据问题的复杂性和大规模性,设计开发了一种基于kNN思想的类标签启发式算法求解模型,拓展了构造路径的方法。算例数值结果表明,本文所设计模型和算法是有效性、可行的。     

考虑绕行特征的电动汽车快速充电站选址问题及自适应遗传算法

快速充电站选址是电动汽车运营的重要内容之一。本文考虑电动汽车用户会通过绕行一定距离对车辆进行充电这一特征,建立了一个以电动汽车快速充电站建站成本和旅客整体绕行成本之和最小的双层整数规划模型。本文首先给出了用于生成绕行路径集合的A^*算法,然后设计了一种包含局部迭代搜索的自适应遗传算法对该模型进行求解。为了测试算法性能,通过两个不同规模的算例图与已有求解FPLM问题的遗传算法进行了比较,数值试验部分证明了算法的正确性和有效性。最后引入浙江省的高速路网图,从建站成本和截流量两方面对电池续航里程带来的影响进行了相关的灵敏度分析。     

带时效性约束的配送中心多源选址问题研究

应用启发式算法求解带时效性约束的多源选址问题.分析物流配送的时效性问题,建立带时效性约束的配送中心多源选址模型.构造两步启发式算法:1)借助传统迭代算法,求解物流服务分配矩阵,把多源选址问题转化为单源选址问题;2)基于M ATLAB函数,设计优化程序,计算带时效性约束的单源选址模型.并给出算例,验证模型和算法的可行性.研究表明两步启发式算法是求解带时效性约束的物流配送中心多源连续选址问题的有效算法.     

考虑共同客户的协同配送优化方法研究

本文针对一些客户仅需要一个配送中心提供配送服务，而某些客户需要多个配送中心提供配送服务(需要多个配送中心提供服务的客户就是企业的共同客户)的情形，提出了一类具有多配送中心、有时间窗限制的车辆路径问题，建立了相应的数学模型。基于“先分类，后求解”的思想，本文设计了两阶段启发式算法：第一阶段提出基于客户聚类的启发式算法，形成聚类信息，将多中心问题转化成单中心问题；第二阶段通过改进的蚁群算法对每个配送中心的情况进行求解。最后，通过算例对该模型的可行性和有效性进行了验证，结果表明与非协同配送方式相比，在配送距离、降低配送成本、提高客户满意度等方面均有明显改进。     

基于可变建设成本的风险共担选址—库存模型研究

在固定建设成本风险共担选址-库存问题(Location model of risk pooling,LMRP)研究基础上,本文从优化角度将配送中心建设成本设为配送中心规模的线性函数,将模型扩展为可变建设成本风险共担选址—库存问题(Location model of risk pooling based on variable construction cost,LMRPVCC),构建非线性0-1整数规划模型。采用启发式粒子群算法求解模型,对经典文献算例进行测算,并依据计算结果,对影响模型目标值的相关参数进行敏感性分析。     

基于时间满意度的应急物资储备库选址问题

基于应急物资配送过程中时间因素的重要性,将时间满意度引人应急物资储备库选址问题中.针对时间满意度为线性分段函数,建立了以时间满意度最小的需求点的时间满意度尽量大以及系统总费用最小为目标的双目标混合整数规划模型,对目标函数的最小最大值问题进行转化,在此基础上构造新的优化模型,并设计了相应的启发式算法求解.最后通过算例说明算法的可行性和有效性.     

基于人工蜂群算法的配送中心选址问题求解

采用人工蜂群算法对配送中心选址问题进行求解,给出食物源的编码方法,通过整数规范化,使算法能在整数空间内对问题进行求解.应用算法进行了仿真实验,并将结果与其它一些启发式算法进行了比较和分析.计算结果表明人工蜂群算法可以有效求解配送中心选址问题,同时也为算法求解其它一些组合优化问题提供了有益思路.     

多阶响应下军事物流配送中心可靠选址模型

为了提高战时物资配送的敏捷性和可靠性,结合军事物资配送的多阶响应过程,以部队用户对配送响应的时间约束为限制条件,以设施固定成本与期望配送成本之和为目标函数,并考虑设施未来失效的可能,建立了混合整数规划形式的军事物流配送中心可靠选址模型.结合模型的特点,采用基于时间约束的启发式算法将模型转化为可行子问题进行求解,使用仿真算例说明模型的优越性和算法的有效性.与不考虑设施失效的选址模型相比,考虑设施失效的选址方案在出现设施失效时,其应急配送成本平均增加量基本不超过设施固定成本的20％,平均最大增加量不超过25％;同一种失效情景下,考虑设施失效的选址方案的应急配送总成本也明显小于不考虑设施失效的选址方案的总成本.     

基于情景分析的应急两级车辆路径问题研究

为研究应急配送过程中次生灾害情景下的车辆路径问题,考虑当地配送中心最后完成救援物资配送任务的时间期望最小化为目标,构建了最小最大两级车辆路径随机规划模型.针对面临的塌方道路抢通时间是随机变量的情况,提出了解决该随机规划的三阶段决策方法:首先建立受灾区域配送点组合情景与随机抢通时间组合情景的关系模型,提出了路径计划策略;其次,提出了针对最小最大两级车辆路径问题的启发式算法;最后,确定每种情景发生的概率,得到最后当地配送中心最后完成救援物资配送任务的时间期望最小化的近似最优解.实验算例验证了该方法的可行性.     

第三方库存-路线问题的模型及混合遗传算法设计

根据第三方库存-路线问题的特点,以车辆租赁费用和运行费用之和为目标函数,不限制客户每次的配送量小于车辆容量,建立了满载运输和非满载运输混合的整数规划模型.针对第三方库存-路线问题的复杂性,本文设计嵌入禁忌搜索的遗传算法来同时决策库存和路线问题.首先对配送间隔进行编码,然后用禁忌搜索法计算每天需要配送的车辆路线问题.最后与其下界值进行比较,结果表明该算法是一个有效的算法,不但第三方能取得较低的运营总成本和较高的车辆利用率,而且也能为客户节约库存空间.     

A bi-level programming model and solution algorithm for the location of logistics distribution centers

In this paper, by considering benefits of customers and logistics planning departments, a bi-level programming model is presented to seek the optimal location for logistics distribution centers. The upper-level model is to determine the optimal location by minimizing the planners’ cost, and the lower gives an equilibrium demand distribution by minimizing the customers’ cost. Based on the special form of constraints, a simple heuristic algorithm is proposed. Finally, a numerical example is used to illustrate the application of the method, which shows that the algorithm is feasible and advantageous.     

Vehicle routing considerations in distribution system design

In Distribution System Design, one minimizes total costs related to the number, locations and sizes of warehouses, and the assignment of warehouses to customers. The resulting system, while optimal in a strategic sense, may not be the best choice if operational aspects such as vehicle routing are also considered.We formulate a multicommodity, capacitated distribution planning model as anon-linear, mixed integer program. Distribution from factories to customers is two-staged via depots (warehouses) whose number and location must be chosen. Vehicle routes from depots to customers are established by considering the “fleet size and mix” problem, which also incorporates strategic decisions on fleet makeup and vehicle numbers of each type. This problem is solved as a generalized assignment problem, within an algorithm for the overall distribution/routing problem that is based on Benders decomposition. We furnish two version of our algorithm denoted Technique I and II. The latter is an enhaancement of the former and is employed at the user's discretion. Computer solution of test problems is discussed.     

Incorporating inventory and routing costs in strategic location models

We consider a supply chain design problem where the decision maker needs to decide the number and locations of the distribution centers (DCs). Customers face random demand, and each DC maintains a certain amount of safety stock in order to achieve a certain service level for the customers it serves. The objective is to minimize the total cost that includes location costs and inventory costs at the DCs, and distribution costs in the supply chain. We show that this problem can be formulated as a nonlinear integer programming model, for which we propose a Lagrangian relaxation based solution algorithm. By exploring the structure of the problem, we find a low-order polynomial algorithm for the nonlinear integer programming problem that must be solved in solving the Lagrangian relaxation sub-problems. We present computational results for several instances of the problem with sizes ranging from 40 to 320 customers. Our results show the benefits of having an integrated supply chain design framework that includes location, inventory, and routing decisions in the same optimization model.     

Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.     

考虑退货不确定性的多层次多站点逆向物流网络选址优化研究

在退货量不确定情况下,为追求电商企业逆向物流网络成本最小化,建立了多层次多站点的混合整数规划模型。将目标区域进行网格化处理,通过球上距离公式计算相邻备选站点、不同层次备选点间的运输距离,使用蒙特卡罗法模拟退货量,并设计了双染色体编码的遗传算法进行求解。算例验证了模型算法的可行性,并且得出了逆向物流网络成本最小时,快递站点和退货处理中心的选址,快递站点的选址与退货量大小存在对应关系,研究客户退货量会使物流网络选址得到优化。     

The plant location problem with demand-dependent setup costs and centralized allocation

Suppose that customers are situated at the nodes of a transportation network, and a service company plans to locate a number of facilities that will serve the customers. The objective is to minimize the sum of the total setup cost and the total transportation cost. The setup cost of a facility is demand-dependent, that is, it depends on the number of customers that are served by the facility. Centralized allocation of customers to facilities is assumed, that is, the service company makes a decision about allocation of customers to facilities. In the case of a general network, the model can be formulated as a mixed integer programming problem. For the case of a tree network, we develop a polynomial-time dynamic programming algorithm.     

基于低碳排放的车辆路径优化问题研究

研究了基于低碳排放的锦州JS配送公司的车辆路径优化问题.首先通过分析目前锦州JS配送公司的车辆路径规划方案发现该公司在规划路径时只关注路径最短,而忽视了碳排放成本.然后通过具体分析配送过程中能源消耗的来源,考虑车辆自重和载重、车辆出行距离等对配送能源消耗的影响,建立了以极小化碳排放成本为目标的车辆路径优化问题的混合整数规划模型,通过求解模型得到新的配送路径优化方案.优化后的配送方案比原先的配送方案减少了14.16万元的碳排放成本.研究结果对物流企业降低碳排放具有指导意义.     

基于两阶段求解策略的动态电动车辆路径优化研究

由于政府对新能源汽车的补贴政策和市区对燃油车限行政策的实时,越来越多的物流公司在城市配送中广泛采用电动汽车。然而,电动车续航里程受限,需要在途充电或者换电,同时客户需求的动态性以及充/换电设施的排队等现实因素也应该被考虑。为此,提出了分阶段策略求解动态电动车辆路径优化问题,并建立了两阶段的EVRP模型。其中第一阶段针对静态客户建立了静态EVRP模型,第二阶段在设计了换电站及动态客户插入策略的基础上,建立了动态EVRP模型以路径更新策略。最后,设计改进的CW-TS混合启发式算法来求解静态模型,设计贪婪算法求解动态模型。实验结果表明,模型与算法具有较好的适用性和有效性。     

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.