带时间窗取送货问题的混合算法  

Hybrid Algorithms for the Pickup and Delivery Problem with Time Windows

作　　者：边展[1] 张倩[2] 徐奇 靳志宏 BIAN Zhan;ZHANG Qian;XU Qi;JIN Zhi-hong(College ofBusiness Administration,Capital University ofEconomics and Business,Beijing 100070,China;Business School,Beijing Technology and Business University,Beijing 100048,China;Transportation Engineering College,Dalian Maritime University,Dalian 116026,China)

机构地区：[1]首都经济贸易大学工商管理学院,北京100070 [2]北京工商大学商学院,北京100048 [3]大连海事大学交通运输工程学院,辽宁大连116026

出　　处：《运筹与管理》2020年第2期97-107,共11页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(71602130,71572023,71302044)。

摘　　要：为解决带时间窗的取送货问题,建立了集合划分模型,设计列生成算法与启发式规则相结合的CGA混合算法进行求解.首先,放松约束构建主问题及受限主问题,运用单纯形法与分支定界进行求解;其次,建立时空网络以构建子问题,基于修正的Dijkstra's算法,设计包含算法A、B1、B2的求解算法;最后,通过启发式算法解决节点重复覆盖问题.为验证算法有效性,进一步构建了OPT近似最优解算法;并基于CGA提出三种求解策略C1、C2、C3,做单因素方差分析,采用算例分析算法的性能.实验结果表明,对于客户点数量小于30的小规模算例,CGA与OPT所得结果相近,但CGA求解效率更显著;针对客户点数量为600的大规模算例,CGA至多在20分钟内求得结果,可见本文算法的精度和效率较高.而针对不同类型及规模的客户点的单因素方差分析结果显示,C1、C2、C3在"平均行驶距离成本"、"平均车辆数"、"平均求解时间"三个维度上差异性显著,经营者可根据实际需求进行策略选择.In order to solve the pickup and delivery problem with time windows,a set partition model is built.A hybrid algorithm CGA which combines the column generation algorithm and heuristic rules is designed to solve the problem.First of all,the main problem and the restricted main problem are constructed by relaxing con-straints,and simplex method and branch-bound are used to solve the problem.Second,the sub-problem is constructed with the space network,and algorithms A,B1,B2 based on the modified Dijkstra's algorithm are designed.At last,heuristics are used to solve the nodes overlap problem.In order to verify the validity of the algorithm,an approximate optimal algorithm OPT is further constructed.Based on the CGA,three solving strate-gies C1,C2 and C3 are proposed to execute the one-way ANOVA.Numerical examples are used to analyze the performance of the algorithm.The analysis result shows that for the small-scale cases with less than 30 customers,the results obtained by CGA and OPT are similar but the CGA has more significant efficiency.For the large-scale cases with up to 600 customers,the CGA can get the result within 20 minutes The result shows that the proposed algorithm is more accurate and efficient.For the different types and sizes of customers,the one-way ANOVA result shows that C1,C2 and C3 are significantly different in the three dimensions of“average travelling cost”,“average number of vehicles”and“average computing time”.Operators can choose the tactics according to the actual demands.

关 键 词：公路运输 取送货问题 时间窗 调度优化 列生成法 启发式算法 

分 类 号：U492.22[交通运输工程—交通运输规划与管理]