节点具有双重需求的车辆路径问题研究
|
摘要
标准车辆路径问题只考虑商品的配送不考虑废弃物的回收，即只存在货物的正向流动。而受人们环境保护意识的加强、废物再利用所带来的附加经济效益等因素的影响，近些年逆向物流越来越受到人们的关注。在存在逆向物流的环境中，有一种情形是客户点一方面需要车辆对之进行商品的配送，另一方面还需要车辆从它那里收集废弃的商品或可再循环使用的材料，这就导致了当车辆对其进行服务时既需要按照客户点的需要进行送货同时还要将客户点处的货物收集起来带走。当考虑服务的对象是这样一些客户点的时候，对车辆路径进行规划的问题，本文将之统称为“节点具有双重需求的车辆路径问题（vehicle routing problem withnodes having double demands，VRPNDD）”。
由于车辆路径问题（vehicle routing problem，VRP）是NP难问题，且VRP问题是VRPNDD问题在节点需求其中一个为0时的特殊情况，所以VRPNDD问题在一般情况下也是NP难的。在VRP问题中当问题规模比较大的时候，即客户节点个数大于100的时候，采用大多数的精确算法求得精确解已经比较困难，而实际当中的问题很多是大规模问题，所以对VRP问题的启发式算法的研究一直以来都是人们关注的焦点。对实际当中的VRPNDD问题的求解一般也要依靠启发式算法，但是在某些特殊情况下，VRPNDD问题是否存在多项式时间的算法，如果存在那么此时就不必设计启发式算法了。因此对VRPNDD问题的研究应该包括特殊情况下问题的计算复杂性的研究。由于VRPNDD问题节点处存在集货、送货双重需求，这一重要属性使得该问题存在一些新的结构性质，而且求解较之节点只具有送货需求的VRP问题更复杂，这就促使了本文对VRPNDD问题的一些基本性质的研究和基于这些性质的启发式算法的设计。本文主要的研究工作及成果有：
（1）对车辆容量为1和大于等于2时的VRPNDD问题的计算复杂性进行了研究。得到车辆容量为1时，在距离对称且满足三角不等式的条件下VRPNDD问题存在多项式时间算法，当容量大于等于2时，即便距离对称且满足更严格的三角不等式，VRPNDD问题仍然是NP难的。
（2）对车辆容量为1和大于等于2时的VRPNDD问题的可简化性进行了研究。得到车辆容量为1时，在距离对称且满足三角不等式的条件下，VRPNDD问题可以简化，当容量大于等于2时，在距离对称且满足三角不等式的条件下，VRPNDD问题不可以简化。
（3）基于集送货需求可拆分车辆路径问题（vehicle routing problem with splitdeliveries and pickups，SVRPPD）解的特点，设计了两种构造型启发式算法：车辆数无限制条件下的最远点拼车贪婪算法和允许车辆数无限制的竞争决策算法。通过数值实验说明了最远点拼车贪婪算法相对于已有的最远点完全拼车算法和最近点完全拼车算法在路径长度优化方面具有优势，但是使用车辆数偏多，适合应用于时间性比较强的环境条件下，而竞争决算法的求解结果在保证车辆使用数最小的情况下仍然使得路径长度最短。接着使用竞争决策算法对现有SVRPPD标准算例进行了测试，并和已有的启发式算法进行了对比，也收到了很好的效果。
（4）对带时间窗集送货需求可拆分车辆路径问题（vehicle routing problem withsplit deliveries and pickups and time windows，SVRPPDTW）进行了研究，提出了贪婪算法、两阶段算法和竞争决策算法。在带时间窗车辆路径问题（vehicle routing problem with time windows，VRPTW）的标准算例的基础上生成了新的适合于求解节点具有双重需求情况下带时间窗问题的算例。提出的算法在新生成的算例的基础上进行了测试，并采用CPLEX优化软件对模型下界进行了求解。结果表明，在规模较小的情况下贪婪算法、两阶段算法计算效果良好，但是随着规模增大竞争决策算法较前两者优势明显增加，但是与问题的下界偏差也增大。
（5）对同时送取货车辆路径问题（vehicle routing problem with simultaneousdelivery and plckup，VRPSDP）的算法进行了综述研究。研究表明目前对于具有内在并行性的现代启发式算法的并行程序设计尚显不足，此外，对于VRPSDP的串行算法的改良应该从寻找更好初始解和寻求有效混合算法的角度着手。
（6）设计了求解VRPSDP问题的竞争决策算法。通过对标准算例的测试的结果与已有的构造型启发式算法的结果对比发现，竞争决策算法适合用于求解客户节点呈群聚式分布的情况。
In the classic vehicle routing problem (VRP), only the commodity’s delivery isconcerned about without the waste material’s recycling. But as the awareness ofenvironmental protection is enhanced and the waste goods’ usage can bring aboutadditional economic benefit, the reverse logistics is paid attention to more and more inthe recent years. In the environment where the reverse logistics exists, there is one casethat the customer ont only need the vehicle to distribute commdities to it but also needthe vehicle to collect the waste or the reusable materials from it, which leads to thevehicle should deliver goods according to the customers’ demand and bring away theuseless goods at the customer while serving it. When the served objects are somecustomers with double demands as above, the corresponding vehicle routing problemis called “the vehicle routing problem with nodes having double demands” abbreviatedas VRPNDD.
Because VRP is NP-hard and VRP is the special case of VRPNDD when either ofthe demands is equal to zero, VRPNDD is NP-hard also in general conditions. In VRP,when the problem’s size is large, that is to say, the number of customers is greater than100, it is has already been very difficult to solve the problem for most of exactalgorithms. Most ot the actual problems in the real world are large-size problems, sothe heuristics is always focused by the people. To solve VRPNDD in the real worldneed to depend on the heuristics generally speaking, but under some special cases,does VRPNDD have polynomial algorithm? If it does, it is not necessary to design theheuristics. So the research about VRPNDD should contain the problem’s complexityunder the special case. The important attribute of the delivery and pickup doubledemands make VRPNDD has some new constructive properties and it is more complexto solve compared to VRP in which the customer has only delivery demand. So someresearches about the basic properties of VRPNDD should be done and the heuristicsbased on these properties should be designed. The main work and results in this paperare:
(1) Researches about the computational complexity under the case that the vehicle’scapacity is equal to1and greater than or equal to2are done. The results show thatwhen the vehicle’s capacity is equal to1, and the distances are symmetric and satisfy the triangle inequality, VRPNDD has polynomial algorithm, but when thecapacity is greater than or equal to2, VRPNDD is NP-hard even if the distance issymmetric and satisfies the sharpened inequality.
(2) Researches about the reducibility under the case that the vehicle’s capacity is equalto1and greater than or equal to2are done. The results show that when thevehicle’s capacity is equal to1and the distances are symmetric and satisfy thetriangle inequality, VRPNDD is reducible, but when the capacity is greater than orequal to2and the distances are symmetric and satisfy the triangle inequality,VRPNDD is unreducible.
(3) Based on the characteristics of the solutions for the vehicle routing problem withsplit deliveries and pickups (SVRPPD), two constructive heuristics: the farthestnode split load algorithm (FNSL) without the limitation of used vehicles’ numberand the competitive decision algorithm (CDA) permitting the used vehicles’number unlimited are designed. The computing experiments show that FNSL hasbetter performance on the optimization of total travel distance compared with theexisted algorithms, i.e. the farthest node full split algorithm (FNFL) and the nearestnode full split algorithm (NNFL), but the used vehicles number is more than theother two algorithms’, which shows that FNSL is applicable to the environmentwhere the time is restricted strictly. CDA’s solutions can guarantee the traveldistances is the shortest under the condition that the used vehicles number is theleast. Then CDA is used to test the benchmark of SVRPPD, and some comparisonsare done with the existed heuristics and the solutions show that CDA has excellentperformance.
(4) Researches about the vehicle routing problem with split deliveries and pickups andtime windows (SVRPPDTW) are done. Greedy algorithm (GA), two stagealgorithm (TS) and CDA are designed to solve SVRPPDTW. Based on thebenchmark of the vehicle routing problem with time windows (VRPTW), somenew instances adapted to VRPNDD with time windows are generated. Theproposed algorithms are tested on the new instances and the CPLEX optimizationsoftware are used to solve the lower bound model. The results show that GA andTS performance well under the condition that the problem’s size is small, butCDA’s superiority increases as the problem size’s increasing, but the gap with thelower bound increases too.
(5) An overview about the vehicle routing problem with simultaneous deliveries andpickups (VRPSDP) are given. The research results of the overview show that theparallel algorithms’ research and designment about the metaheuristics withparallelism in it are not enough and the improvement for the serial algorithmsshould be done in two aspects, i.e. searching for better initial solutions andsearching for valid hybrid algorithms.
(6) CDA algorithms of VRPSDP are designed. The comparisons among the testedresults of the existed constructive heuristics and CDA on the VRPSDP benchmarkshow that CDA performs well under the condition that the customers locations areclustered.
由于车辆路径问题（vehicle routing problem，VRP）是NP难问题，且VRP问题是VRPNDD问题在节点需求其中一个为0时的特殊情况，所以VRPNDD问题在一般情况下也是NP难的。在VRP问题中当问题规模比较大的时候，即客户节点个数大于100的时候，采用大多数的精确算法求得精确解已经比较困难，而实际当中的问题很多是大规模问题，所以对VRP问题的启发式算法的研究一直以来都是人们关注的焦点。对实际当中的VRPNDD问题的求解一般也要依靠启发式算法，但是在某些特殊情况下，VRPNDD问题是否存在多项式时间的算法，如果存在那么此时就不必设计启发式算法了。因此对VRPNDD问题的研究应该包括特殊情况下问题的计算复杂性的研究。由于VRPNDD问题节点处存在集货、送货双重需求，这一重要属性使得该问题存在一些新的结构性质，而且求解较之节点只具有送货需求的VRP问题更复杂，这就促使了本文对VRPNDD问题的一些基本性质的研究和基于这些性质的启发式算法的设计。本文主要的研究工作及成果有：
（1）对车辆容量为1和大于等于2时的VRPNDD问题的计算复杂性进行了研究。得到车辆容量为1时，在距离对称且满足三角不等式的条件下VRPNDD问题存在多项式时间算法，当容量大于等于2时，即便距离对称且满足更严格的三角不等式，VRPNDD问题仍然是NP难的。
（2）对车辆容量为1和大于等于2时的VRPNDD问题的可简化性进行了研究。得到车辆容量为1时，在距离对称且满足三角不等式的条件下，VRPNDD问题可以简化，当容量大于等于2时，在距离对称且满足三角不等式的条件下，VRPNDD问题不可以简化。
（3）基于集送货需求可拆分车辆路径问题（vehicle routing problem with splitdeliveries and pickups，SVRPPD）解的特点，设计了两种构造型启发式算法：车辆数无限制条件下的最远点拼车贪婪算法和允许车辆数无限制的竞争决策算法。通过数值实验说明了最远点拼车贪婪算法相对于已有的最远点完全拼车算法和最近点完全拼车算法在路径长度优化方面具有优势，但是使用车辆数偏多，适合应用于时间性比较强的环境条件下，而竞争决算法的求解结果在保证车辆使用数最小的情况下仍然使得路径长度最短。接着使用竞争决策算法对现有SVRPPD标准算例进行了测试，并和已有的启发式算法进行了对比，也收到了很好的效果。
（4）对带时间窗集送货需求可拆分车辆路径问题（vehicle routing problem withsplit deliveries and pickups and time windows，SVRPPDTW）进行了研究，提出了贪婪算法、两阶段算法和竞争决策算法。在带时间窗车辆路径问题（vehicle routing problem with time windows，VRPTW）的标准算例的基础上生成了新的适合于求解节点具有双重需求情况下带时间窗问题的算例。提出的算法在新生成的算例的基础上进行了测试，并采用CPLEX优化软件对模型下界进行了求解。结果表明，在规模较小的情况下贪婪算法、两阶段算法计算效果良好，但是随着规模增大竞争决策算法较前两者优势明显增加，但是与问题的下界偏差也增大。
（5）对同时送取货车辆路径问题（vehicle routing problem with simultaneousdelivery and plckup，VRPSDP）的算法进行了综述研究。研究表明目前对于具有内在并行性的现代启发式算法的并行程序设计尚显不足，此外，对于VRPSDP的串行算法的改良应该从寻找更好初始解和寻求有效混合算法的角度着手。
（6）设计了求解VRPSDP问题的竞争决策算法。通过对标准算例的测试的结果与已有的构造型启发式算法的结果对比发现，竞争决策算法适合用于求解客户节点呈群聚式分布的情况。
In the classic vehicle routing problem (VRP), only the commodity’s delivery isconcerned about without the waste material’s recycling. But as the awareness ofenvironmental protection is enhanced and the waste goods’ usage can bring aboutadditional economic benefit, the reverse logistics is paid attention to more and more inthe recent years. In the environment where the reverse logistics exists, there is one casethat the customer ont only need the vehicle to distribute commdities to it but also needthe vehicle to collect the waste or the reusable materials from it, which leads to thevehicle should deliver goods according to the customers’ demand and bring away theuseless goods at the customer while serving it. When the served objects are somecustomers with double demands as above, the corresponding vehicle routing problemis called “the vehicle routing problem with nodes having double demands” abbreviatedas VRPNDD.
Because VRP is NP-hard and VRP is the special case of VRPNDD when either ofthe demands is equal to zero, VRPNDD is NP-hard also in general conditions. In VRP,when the problem’s size is large, that is to say, the number of customers is greater than100, it is has already been very difficult to solve the problem for most of exactalgorithms. Most ot the actual problems in the real world are large-size problems, sothe heuristics is always focused by the people. To solve VRPNDD in the real worldneed to depend on the heuristics generally speaking, but under some special cases,does VRPNDD have polynomial algorithm? If it does, it is not necessary to design theheuristics. So the research about VRPNDD should contain the problem’s complexityunder the special case. The important attribute of the delivery and pickup doubledemands make VRPNDD has some new constructive properties and it is more complexto solve compared to VRP in which the customer has only delivery demand. So someresearches about the basic properties of VRPNDD should be done and the heuristicsbased on these properties should be designed. The main work and results in this paperare:
(1) Researches about the computational complexity under the case that the vehicle’scapacity is equal to1and greater than or equal to2are done. The results show thatwhen the vehicle’s capacity is equal to1, and the distances are symmetric and satisfy the triangle inequality, VRPNDD has polynomial algorithm, but when thecapacity is greater than or equal to2, VRPNDD is NP-hard even if the distance issymmetric and satisfies the sharpened inequality.
(2) Researches about the reducibility under the case that the vehicle’s capacity is equalto1and greater than or equal to2are done. The results show that when thevehicle’s capacity is equal to1and the distances are symmetric and satisfy thetriangle inequality, VRPNDD is reducible, but when the capacity is greater than orequal to2and the distances are symmetric and satisfy the triangle inequality,VRPNDD is unreducible.
(3) Based on the characteristics of the solutions for the vehicle routing problem withsplit deliveries and pickups (SVRPPD), two constructive heuristics: the farthestnode split load algorithm (FNSL) without the limitation of used vehicles’ numberand the competitive decision algorithm (CDA) permitting the used vehicles’number unlimited are designed. The computing experiments show that FNSL hasbetter performance on the optimization of total travel distance compared with theexisted algorithms, i.e. the farthest node full split algorithm (FNFL) and the nearestnode full split algorithm (NNFL), but the used vehicles number is more than theother two algorithms’, which shows that FNSL is applicable to the environmentwhere the time is restricted strictly. CDA’s solutions can guarantee the traveldistances is the shortest under the condition that the used vehicles number is theleast. Then CDA is used to test the benchmark of SVRPPD, and some comparisonsare done with the existed heuristics and the solutions show that CDA has excellentperformance.
(4) Researches about the vehicle routing problem with split deliveries and pickups andtime windows (SVRPPDTW) are done. Greedy algorithm (GA), two stagealgorithm (TS) and CDA are designed to solve SVRPPDTW. Based on thebenchmark of the vehicle routing problem with time windows (VRPTW), somenew instances adapted to VRPNDD with time windows are generated. Theproposed algorithms are tested on the new instances and the CPLEX optimizationsoftware are used to solve the lower bound model. The results show that GA andTS performance well under the condition that the problem’s size is small, butCDA’s superiority increases as the problem size’s increasing, but the gap with thelower bound increases too.
(5) An overview about the vehicle routing problem with simultaneous deliveries andpickups (VRPSDP) are given. The research results of the overview show that theparallel algorithms’ research and designment about the metaheuristics withparallelism in it are not enough and the improvement for the serial algorithmsshould be done in two aspects, i.e. searching for better initial solutions andsearching for valid hybrid algorithms.
(6) CDA algorithms of VRPSDP are designed. The comparisons among the testedresults of the existed constructive heuristics and CDA on the VRPSDP benchmarkshow that CDA performs well under the condition that the customers locations areclustered.
引文
[1]李亚.“两化”融合加速推进物流企业转型迎契机.现代物流报,2012.7.16.
[2] Dantzig GB, Ramser JH. The Truck Dispatching Problem. Management Science,1959,6(1):80-91.
[3] Lenstra JK, Kan AHG. Complexity of vehicle routing and secheduling problems.Networks,1981,11(2):221-227.
[4] Hall R. On the road to integration. OR/MS Today,2006,33(3):50-57.
[5]邢文训，谢金星.现代优化计算方法.北京:清华大学出版社（第二版）,2005.
[6]孙小玲，李端.整数规划.北京:科学出版社,2010.
[7] Golden B, Raghavan S, Wasil E. The vehicle routing problem: latest advances andnew challenges. Berlin: Springer-Verlag,2008.
[8] Magnanti TL. Combinatorial optimization and vehicle fleet planning: Perspectivesand prospects. Networks,1981,11(2):179-213.
[9] Dantzig GB, Fulkerson DR, Johnson SM, Solution of a Large Scale TravellingSalesman Problem. Operations Research,1954,2(4):393–410.
[10] Laporte G, Nobert Y. Exact algorithms for the vehicle routing problem. Annals ofDiscrete Mathematics,1987,31:147–184.
[11] Laporte G, Mercure H, Nobert Y. An exact algorithm for the asymmetricalcapacitated vehicle routing problem. Networks,1986,16(1):33-46.
[12] Agarwal Y, Mathur K, Salkin HM. A set-partitioning-based exact algorithm for thevehicle routing problem. Networks,1989,19(7):731-749.
[13] Roberto B, Aristide M, Roberto R. Recent exact algorithms for solving the vehiclerouting problem under capacity and time window constraints. European Journal ofOperational Research,2012,218(1):1-6.
[14] Baldacci R, Hadjiconstantinou E, Mingozzi A. An exact algorithm for thecapacitated vehicle routing problem based on a two-commodity network flowformulation. Operations Research,2004,52(5):723–738.
[15] Balinski ML, Quandt RE. On an integer program for a delivery problem.Operations Research,1964,12(2):300–304.
[16] Gendreau M, Potvin JY, Br umlaysy O, Hasle G, L kketangen A. Metaheuristicsfor the vehicle routing problem and its extensions: a categorized bibliography. TheVehicle Routing Problem: Latest Advances and New Challenges. Berlin: Springer-Verlag,2008:143-169.
[17]李相勇.车辆路径问题模型及算法研究.上海交通大学博士学位论文,2007.
[18]刘冉.面向协同运输的车辆路径问题优化算法研究.上海交通大学博士学位论文,2011.
[19] Jun Y, Kim BI. New best solutions to VRPSPD benchmark problems by aperturbation based algorithm. Expert Systems with Applications,2012,39(5):5641-5648.
[20] Montane FAT, Galvao RD. A tabu search algorithm for the vehicle routingproblem with simultaneous pick-up and delivery service. Computers&OperationsResearch,2006,33(3):595–619.
[21] Potvin JY, Kervahut T, Garcia BL and Rousseau JM. A tabu search heuristic forthe vehicle routing problem with time windows. Technical Report CRT-855, Universitede Montreal, Quebec, Canada,1992.
[22] Lin S. Computer solutions to the travelling salesman problem. Bell SystemTechnology Journal,1965,44:2245–2269.
[23] Or I. Traveling salesman-type combinatorial problems and their relation to thelogistics of regional blood banking. Ph.D. thesis, Department of Industrial Engineeringand Management Sciences, Northwestern University, Evanston, IL,1976.
[24]陈国良.并行算法的设计与分析（第3版）.北京:高等教育出版社,2009.
[25] Ralphs TK, Ladanyi L, Saltzman MJ. Parallel branch, cut, and price for large-scale discrete optimization. Mathematical Programming,2003,98(1-3):253–280.
[26] Ralphs TK. Parallel branch and cut for capacitated vehicle routing. ParallelComputing,2003,29(5):607-629.
[27] Ralphs TK, Ladanyi L, Saltzman MJ. A library hierarchy for implementingscalable parallel search algorithms. The Journal of Super Computing,2004,28(2):215–234.
[28] Greening DR. Parallel simulated annealing techniques. Physica D: NonlinearPhenomena,1990,42(1-3):293–306.
[29] Verhoeven MGA, AARTS EHL. Parallel local search. Journal of Heuristics,1995,1(1):43–65.
[30] Crainic TG, Toulouse M, Gendreau M. Towards a taxonomy of parallel tabu searchalgorithms. INFORMS Journal on Computing,1997,9(1):61–72.
[31] Crainic TG, Toulouse M. Parallel strategies for meta-heuristics. Handbook inMetaheuristics. Norwell: Kluwer Academic Publishers,2003:475-513.
[32]Crainic TG. Parallel computation, co-operation, tabu search. MetaheuristicOptimization Via Memory and Evolution：Tabu Search and Scatter Search. Norwell:Kluwer Academic Publishers,2005:283-302.
[33] Crainic TG. Parallel solution methods for vehicle routing problems. The VehicleRouting Problem: Latest Advances and New Challenges. Berlin: Springer-Verlag,2008:171–198.
[34] Mingozzi A, Giorgi S, Baldacci R. An exact method for the vehicle routingproblem with backhauls. Transportation Science,1999,33(3):315–329.
[35] Brandao J. A new tabu search algorithm for the vehicle routing problem withbackhauls. European Journal Operational Research,2006,173(2):540–555.
[36] Salhi S, Nagy G. A cluster insertion heuristic for single and multiple depot vehiclerouting problems with backhauling. Journal of the Operational Research Society,1999,50(10):1034–1042.
[37] Wade AC, Salhi S. An investigation into a new class of vehicle routing problemwith backhauls. Omega,2002,30(6):479–487.
[38] Subramanian A, Uchoa E, Pessoa AA, Ochi LS. Branch-and-cut with lazyseparation for the vehicle routing problem with simultaneous pickup and delivery.Operations Research Letters,2011,39(5):338-341.
[39] Dethloff J. Vehicle routing and reverse logistics: the vehicle routing problem withsimultaneous delivery and pick-up. OR Spektrum,2001,23(1):79–96.
[40] Catay B. A new saving-based ant algorithm for the vehicle routing problem withsimultaneous pickup and delivery. Expert Systems with Applications,2010,37(10):6809–6817.
[41] Subramanian A, Drummond LMA, Bentes C, Ochi LS, Farias R. A parallelheuristic for the vehicle routing problem with simultaneous pickup and delivery.Computers&Operations Research,2010,37(11):1899–1911.
[42] Mitra S. An algorithm for the generalized vehicle routing problem withbackhauling. Asia-Pacific Journal of Operational Reasearch,2005,22(2):153-169.
[43] Mitra S. A parallel clustering technique for the vehicle routing problem with splitdeliveries and pickups. Journal of the Operational Research Society,2008,59(11):1532-1546.
[44] Savelsbergh M, Sol M. The general pickup and delivery problem. TransportationScience,1995,29(1):17-29.
[45] Dror M, Trudeau G. Savings by split delivery routing. Transportation Science,1989,23(2):141–145.
[46] Dror M, Trudeau G. Split delivery routing. Naval Research Logistics,1990,37(3):383–402.
[47] Archetti C, Mansini R, Speranza MG. Complexity and reducibility of the skipdelivery problem. Transportation Science,2005,39(2):182-187.
[48] Archetti C, Savelsbergh MWP, Grazia M. Worst-case analysis for split deliveryvehicle routing problems. Transportation Science,2006,40(2):226-234.
[49] Dror M, Laporte G, Trudeau P. Vehicle routing with split deliveries. DiscreteApplied Mathematics,1994,50(3):239–254.
[50] Belenguer JM, Martinez MC, Mota E. A lower bound for the split delivery vehiclerouting problem. Operations Research,2000,48(5):801–810.
[51] Moreno L, Arag o MP, Uchoa E. Improved lower bounds for the split deliveryvehicle routing problem. Operations Research Letters,2010,38(4):302-306.
[52] Bompadre A, Dror M, Orlin JB. Improved bounds for vehicle routing solutions.Discrete Optimization,2006,3(4):299-316.
[53] Lee CG, Epelman MA, White CC, Bozer YA. A shortest path approach to themultiple-vehicle routing problem with split pick-ups. Transportation Research B,2006,40(4):265–284.
[54] Jin M, Liu K, Bowden RO. A two-stage algorithm with valid inequalities for thesplit delivery vehicle routing problem. International Journal of Production Economics,2007,105(1):228-242.
[55] Archetti C, Speranza MG, Hertz A. A tabu search algorithm for the split deliveryvehicle routing problem. Transportation Science,2006,40(1):64-73.
[56] Mota E, Campos V, Corberán A. A new metaheuristic for the vehicle routingproblem with split demands. Proceedings of the7th European conference onEvolutionary computation in combinatorial optimization. Berlin: Springer-Verlag,2007：121–129.
[57] Boudia M, Prins C, Reghioui M. An effective memetic algorithm with populationmanagement for the split-delivery vehicle routing problem. Proceedings of the4thinternational conference on Hybrid metaheuristics. Berlin: Springer-Verlag,2007:16–30.
[58] Archetti C, Savelsbergh MWP, Speranza MG. An optimization-based heuristic forthe split delivery vehicle routing problem. Transportation Science,2008,42(1):22-31.
[59] Chen S, Golden BL, Wasil E. The split delivery vehicle routing problem:applications, algorithms, test problems and computational results. Networks,2007,49(4)318–329.
[60] Archetti C, Savelsbergh MWP, Speranza MG. To split or not to split: that is thequestion. Transportation Research Part E: Logistics and Transportation Review,2008,40(1):114-123.
[61] Mullaseril PA, Dror M, Leung J. Split-delivery routing in livestock feeddistribution. Journal of the Operational Research Society,1997,48(2):107-116.
[62] Sierksma G, Tijssen GA. Routing helicopters for crew exchanges on off-shorelocations. Annals of Operations Research,1998,76(0):261-286.
[63]Archetti C, Speranza MG. Vehicle routing in the1-skip collection problem. Journalof the Operational Research Society,2004,55(7):717-727.
[64] Song S, Lee K, Kim G. A practical approach to solving a newspaper logisticsproblem using a digital map. Comput Ind Eng,2002,43(1-2):315–330.
[65] Min H. The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A,1989,23(5):377–386.
[66]唐国春.新的车辆路径问题.中国运筹学会第九届学术交流会论文集.Hongkong: Global-Link Informatics Limited，2008:269-277．
[67]杨亚璪，靳文舟，郝小妮，田晟.求解集送货可拆分车辆路径问题的启发式算法.华南理工大学学报（自然科学版）,2010,38(3):58-63.
[68]王晓东.计算机算法设计与分析（第3版）.北京:电子工业出版社,2007.
[69] Papadimitriou CH, Steiglitz K. Combinatorial optimization: algorithms andcomplexity. NewJersey: Prentice Hall,1982.
[70]张利昂.NP完全性理论介绍.计算机工程与应用，1984（5）:1-33.
[71] Gary MR, Johnson DS. Computers and Intractability: A Guide to the Theory ofNp-Completeness. San Francisco: W.H.Freeman and company,1979.
[72] Gerards AMH. Matching. Handbooks in Operations Research and ManagementScience. North-Holland, Amsterdam,1995.
[73] Tardos E. A strongly polynomial minimum cost circulation algorithm.Combinatorica.1985,5(3):247-255.
[74]宁爱兵.竞争决策算法及其在组合优化中的应用.上海理工大学博士学位论文,2005.
[75]熊小华.元胞竞争决策算法及其应用研究.上海理工大学博士学位论文,2011.
[76]宁爱兵，马良.度约束最小生成树（DCMST）的竞争决策算法.系统工程学报.2005,20(6):630-634.
[77] Desrosiers J, Soumis F, Desrochers M. Routing with time windows by columngeneration. Networks,1984,14(4):545-565.
[78] Solomon MM. Algorithm for the vehicle routing and scheduling problems withtime window constraints. Operations Research,1987,35(2):254-265.
[79] Olli Br ysy, Michel Gendreau.Vehicle routing problem with time windows, part I:route construction and local search algorithms. Transportation science,2005,39(1):104-118.
[80] Olli Br ysy, Michel Gendreau. Vehicle routing problem with time windows, partII: metaheuristics. Transportation science,2005,39(1):119-139.
[81] Angelelli E, Mansini R. The vehicle routing problem with time windows andsimultaneous pickup and delivery. Quantitative Approaches to Distribution Logisticsand Supply ChainManagement. Berlin: Springer-Verlag,2002:249-267.
[82]马庆国,孟丽君.基于混合算法的具有硬时间窗口约束的VRPSPD问题.西安电子科技大学学报,2009,19(2):41-46．
[83] Lai MY， Cao EB. An improved differential evolution algorithm for vehiclerouting problem with simultaneous pickups and deliveries and time windows.Engineering Applications of Artificial Intelligence,2010,23(2):188-195．
[84]殷佳林,蒋泰.基于蚁群算法求解带硬时间窗的VRPSDP.计算机系统应用，2009,(8):152-155．
[85] Chang MS, Chen SR, Hsueh CF. Real-time vehicle routing problem with timewindows and simultaneous delivey/pickup demands. Journal of the Eastern AsiaSociety，2003,5:2273-2286．
[86] Ho S C, Haugland D. A tabu search heuristic for the vehicle routing problem withtime windows and split deliveries. Computers&Operations Research.2004,31(12):1947-1964.
[87] Grotschel M, Holland O. Solution of large-scale travelling salesman problems.Mathematical Programming,1991,51(2):141-202.
[88] Padberg M, Rinaldi G. A branch-and-cut algorithm for the resolution of large-scalesymmetric traveling salesman problems. SIAM Review,1991,33(1):60-100.
[89] Mitchell, J.E. Branch-and-cut algorithms for combinatorial optimization problems.Handbook of Applied Optimization. New York: Oxford University Press,2002:65–77.
[90] Lysgaard J, Letchford AN, Eglese RW. A new branch-and-cut algorithm for thecapacitated vehicle routing problem. Mathematical Programming,2004,100(2):423–445.
[91] Lysgaard J. CVRPSEP: a package of separation routines for the capacitated vehiclerouting problem. Working Paper,2004,03-04, Department of Business Studies, AarhusSchool of Business, University of Aarhus, Danmark.
[92] Subramanian A, Uchoa E, Ochi LS. New lower bounds for the vehicle routingproblem with simultaneous pickup and delivery. Lecture Notes in Computer Science,2010,6049:276-287.
[93] Subramanian A, Uchoa E, Pessoa AA. Branch-and-cut with lazy separation for theVehicle Routing Problem with Simultaneous Pickup and Delivery. OperationsResearch Letters,2011,39(5):338-341.
[94] Cordier C, Marchand H, Laundy R, et al. bc-opt: A branch-and-cut code for mixedinteger programs. Mathematical Programming,1999,86(2):335-353.
[95]朱道立.大系统优化理论与应用.上海：上海交通大学出版社，1987.
[96] Wilhelm WE. A technical review of column generation in integer programming.Optimization and Engineering,2001,2(2):159-200.
[97] Dell'amico M, Righini G, Salani M. A branch-and-price approach to the vehiclerouting problem with simultaneous distribution and collection. Transportation Science,2006,40(2):235-247.
[98]李晨.带有协作机制的车辆路径问题的分支定价算法.南开大学硕士学位论文，2010.
[99] Nagy G, Salhi S. Heuristic algorithms for single and multiple depot vehiclerouting problems with pickups and deliveries. European Journal of OperationalResearch,2005,162(1):126–141.
[100] Bianchessi N, Righini G. Heuristic algorithms for the vehicle routing problemwith simultaneous pick-up and delivery. Computers&Operations Research,2007,34(2):578–594.
[101] Crispim J, Brandao J. Metaheuristics applied to mixed and simultaneousextensions of vehicle routing problems with backhauls. Journal of the OperationalResearch Society,2005,56(7):1296–302.
[102] Hansen P, Mladenovic N. Variable neighborhood search: principles andapplications. European Journal of Operational Research,2001,130(3):449–467.
[103] Ropke S, Pisinger D. A unified heuristic for vehicle routing problems withbackhauls. European Journal of Operational Research,2006,171(3):750–775.
[104] Wassan NA, Wassan AH, Nagy G. A reactive tabu search algorithm for thevehicle routing problem with simultaneous pickups and deliveries. Journal ofCombinatorial Optimization,2008,15(4):368–386.
[105] Chen JF, Wu TH. Vehicle routing problem with simultaneous deliveries andpickups. Journal of the Operational Research Society,2006,57(5):579–587.
[106] Zachariadis EE, Tarantilis CD, Kiranoudis CT. A hybrid metaheuristic algorithmfor the vehicle routing problem with simultaneous delivery and pick-up service. ExpertSystems with Applications,2009,36(2):1070–1081.
[107] Gribkovskaia I, Halskau, Laporte G, et al. General solutions to the singlevehicle routing problem with pickups and deliveries. European Journal of OperationalResearch,2007,180(2):568–584.
[108] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony ofcooperating agents. IEEE Transactions Systems, Man, and Cybernetics,1996,26(1):29-41.
[109] Bullnheimer B, Hartl RF, Strauss C. Applying the ant system to the vehiclerouting problem. Meta-heuristics: advances and trends in local search paradigms foroptimization. Boston: Kluwer Academic Publishers,1999:285–296.
[110] Wade A, Salhi S. An ant system algorithm for the vehicle routing problems withbackhauls. Proceedings of MIC2001Fourth Metaheuristics International Conference.2001:199–203.
[111] Wade A, Salhi, S. An ant system algorithm for the mixed vehicle routing problemwith backhauls. Metaheuristics: Computer Decision Making. New York: Kluwer,2003:699–719.
[112] Reimann M, Ulrich U. Comparing backhauling strategies in vehicle routingusing ant colony optimization. Central European Journal of Operations Research,2006,14(2):105–123.
[113] Gokce EI. A revised ant colony system approach to vehicle routing problems.Master thesis, Sabanci University, Istanbul, Turkey,2004.
[114] Gajpal Y, Abad P. An ant colony system (ACS) for vehicle routing problem withsimultaneous delivery and pickup. Computers&Operations Research,2009,36(12):3215–3223.
[115]张涛，田文馨，张钥杰，等.基于剩余装载能力的蚁群算法求解同时送取货车辆路径问题.控制理论与应用,2009,26(5):546-549.
[116] Kennedy J, Eberhart R. Particle swarm optimization. Proceedings of IEEEinternational conference on neural networks. Piscataway, IEEE Service Center,1995,4:1942-1948.
[117]纪震，廖惠连，吴青华.粒子群算法及应用.北京：科学出版社，2009.
[118] Ai TJ, Kachitvichyanukul V. A particle swarm optimization for the vehiclerouting problem with simultaneous pickup and delivery. Computers&OperationsResearch,2009,36(5):1693-1702.
[119] Zhang NZ, Sun GH, Wu Y H, et al. A modified particle swarm optimization forthe vehicle routing problem with simultaneous pickup and delivery. Proceedings of the7th Asian Control Conference. Piscataway, IEEE Service Center,2009:1679-1684.
[120] Goksal FP, Karaoglan I, Altiparmak F. A hybrid discrete particle swarmoptimization for vehicle routing problem with simultaneous pickup and delivery.Computers&Industrial Engineering, in press, available online20January2012.
[121] Vural AV. A GA based meta-heuristic for capacitated vehicle routing problemwith simultaneous pick-up and deliveries.Master’s thesis, Sabanci University, Istanbul,Turkey,2003.
[122]彭春林，梁春华，周泓.求解同时取货和送货车辆路径问题的改进遗传算法.系统仿真学报,2008,20(9):2266-2270.
[123] Zachariadis EE, Tarantilis CD, Kiranoudis CT. An adaptive memorymethodology for the vehicle routing problem with simultaneous pick-ups anddeliveries. European Journal of Operational Research,2010,202(2):401–411.
[124] Paessens H. The savings algorithm for the vehicle routing problem. EuropeanJournal of Operational Research,1988,34(3):336–344.
[2] Dantzig GB, Ramser JH. The Truck Dispatching Problem. Management Science,1959,6(1):80-91.
[3] Lenstra JK, Kan AHG. Complexity of vehicle routing and secheduling problems.Networks,1981,11(2):221-227.
[4] Hall R. On the road to integration. OR/MS Today,2006,33(3):50-57.
[5]邢文训，谢金星.现代优化计算方法.北京:清华大学出版社（第二版）,2005.
[6]孙小玲，李端.整数规划.北京:科学出版社,2010.
[7] Golden B, Raghavan S, Wasil E. The vehicle routing problem: latest advances andnew challenges. Berlin: Springer-Verlag,2008.
[8] Magnanti TL. Combinatorial optimization and vehicle fleet planning: Perspectivesand prospects. Networks,1981,11(2):179-213.
[9] Dantzig GB, Fulkerson DR, Johnson SM, Solution of a Large Scale TravellingSalesman Problem. Operations Research,1954,2(4):393–410.
[10] Laporte G, Nobert Y. Exact algorithms for the vehicle routing problem. Annals ofDiscrete Mathematics,1987,31:147–184.
[11] Laporte G, Mercure H, Nobert Y. An exact algorithm for the asymmetricalcapacitated vehicle routing problem. Networks,1986,16(1):33-46.
[12] Agarwal Y, Mathur K, Salkin HM. A set-partitioning-based exact algorithm for thevehicle routing problem. Networks,1989,19(7):731-749.
[13] Roberto B, Aristide M, Roberto R. Recent exact algorithms for solving the vehiclerouting problem under capacity and time window constraints. European Journal ofOperational Research,2012,218(1):1-6.
[14] Baldacci R, Hadjiconstantinou E, Mingozzi A. An exact algorithm for thecapacitated vehicle routing problem based on a two-commodity network flowformulation. Operations Research,2004,52(5):723–738.
[15] Balinski ML, Quandt RE. On an integer program for a delivery problem.Operations Research,1964,12(2):300–304.
[16] Gendreau M, Potvin JY, Br umlaysy O, Hasle G, L kketangen A. Metaheuristicsfor the vehicle routing problem and its extensions: a categorized bibliography. TheVehicle Routing Problem: Latest Advances and New Challenges. Berlin: Springer-Verlag,2008:143-169.
[17]李相勇.车辆路径问题模型及算法研究.上海交通大学博士学位论文,2007.
[18]刘冉.面向协同运输的车辆路径问题优化算法研究.上海交通大学博士学位论文,2011.
[19] Jun Y, Kim BI. New best solutions to VRPSPD benchmark problems by aperturbation based algorithm. Expert Systems with Applications,2012,39(5):5641-5648.
[20] Montane FAT, Galvao RD. A tabu search algorithm for the vehicle routingproblem with simultaneous pick-up and delivery service. Computers&OperationsResearch,2006,33(3):595–619.
[21] Potvin JY, Kervahut T, Garcia BL and Rousseau JM. A tabu search heuristic forthe vehicle routing problem with time windows. Technical Report CRT-855, Universitede Montreal, Quebec, Canada,1992.
[22] Lin S. Computer solutions to the travelling salesman problem. Bell SystemTechnology Journal,1965,44:2245–2269.
[23] Or I. Traveling salesman-type combinatorial problems and their relation to thelogistics of regional blood banking. Ph.D. thesis, Department of Industrial Engineeringand Management Sciences, Northwestern University, Evanston, IL,1976.
[24]陈国良.并行算法的设计与分析（第3版）.北京:高等教育出版社,2009.
[25] Ralphs TK, Ladanyi L, Saltzman MJ. Parallel branch, cut, and price for large-scale discrete optimization. Mathematical Programming,2003,98(1-3):253–280.
[26] Ralphs TK. Parallel branch and cut for capacitated vehicle routing. ParallelComputing,2003,29(5):607-629.
[27] Ralphs TK, Ladanyi L, Saltzman MJ. A library hierarchy for implementingscalable parallel search algorithms. The Journal of Super Computing,2004,28(2):215–234.
[28] Greening DR. Parallel simulated annealing techniques. Physica D: NonlinearPhenomena,1990,42(1-3):293–306.
[29] Verhoeven MGA, AARTS EHL. Parallel local search. Journal of Heuristics,1995,1(1):43–65.
[30] Crainic TG, Toulouse M, Gendreau M. Towards a taxonomy of parallel tabu searchalgorithms. INFORMS Journal on Computing,1997,9(1):61–72.
[31] Crainic TG, Toulouse M. Parallel strategies for meta-heuristics. Handbook inMetaheuristics. Norwell: Kluwer Academic Publishers,2003:475-513.
[32]Crainic TG. Parallel computation, co-operation, tabu search. MetaheuristicOptimization Via Memory and Evolution：Tabu Search and Scatter Search. Norwell:Kluwer Academic Publishers,2005:283-302.
[33] Crainic TG. Parallel solution methods for vehicle routing problems. The VehicleRouting Problem: Latest Advances and New Challenges. Berlin: Springer-Verlag,2008:171–198.
[34] Mingozzi A, Giorgi S, Baldacci R. An exact method for the vehicle routingproblem with backhauls. Transportation Science,1999,33(3):315–329.
[35] Brandao J. A new tabu search algorithm for the vehicle routing problem withbackhauls. European Journal Operational Research,2006,173(2):540–555.
[36] Salhi S, Nagy G. A cluster insertion heuristic for single and multiple depot vehiclerouting problems with backhauling. Journal of the Operational Research Society,1999,50(10):1034–1042.
[37] Wade AC, Salhi S. An investigation into a new class of vehicle routing problemwith backhauls. Omega,2002,30(6):479–487.
[38] Subramanian A, Uchoa E, Pessoa AA, Ochi LS. Branch-and-cut with lazyseparation for the vehicle routing problem with simultaneous pickup and delivery.Operations Research Letters,2011,39(5):338-341.
[39] Dethloff J. Vehicle routing and reverse logistics: the vehicle routing problem withsimultaneous delivery and pick-up. OR Spektrum,2001,23(1):79–96.
[40] Catay B. A new saving-based ant algorithm for the vehicle routing problem withsimultaneous pickup and delivery. Expert Systems with Applications,2010,37(10):6809–6817.
[41] Subramanian A, Drummond LMA, Bentes C, Ochi LS, Farias R. A parallelheuristic for the vehicle routing problem with simultaneous pickup and delivery.Computers&Operations Research,2010,37(11):1899–1911.
[42] Mitra S. An algorithm for the generalized vehicle routing problem withbackhauling. Asia-Pacific Journal of Operational Reasearch,2005,22(2):153-169.
[43] Mitra S. A parallel clustering technique for the vehicle routing problem with splitdeliveries and pickups. Journal of the Operational Research Society,2008,59(11):1532-1546.
[44] Savelsbergh M, Sol M. The general pickup and delivery problem. TransportationScience,1995,29(1):17-29.
[45] Dror M, Trudeau G. Savings by split delivery routing. Transportation Science,1989,23(2):141–145.
[46] Dror M, Trudeau G. Split delivery routing. Naval Research Logistics,1990,37(3):383–402.
[47] Archetti C, Mansini R, Speranza MG. Complexity and reducibility of the skipdelivery problem. Transportation Science,2005,39(2):182-187.
[48] Archetti C, Savelsbergh MWP, Grazia M. Worst-case analysis for split deliveryvehicle routing problems. Transportation Science,2006,40(2):226-234.
[49] Dror M, Laporte G, Trudeau P. Vehicle routing with split deliveries. DiscreteApplied Mathematics,1994,50(3):239–254.
[50] Belenguer JM, Martinez MC, Mota E. A lower bound for the split delivery vehiclerouting problem. Operations Research,2000,48(5):801–810.
[51] Moreno L, Arag o MP, Uchoa E. Improved lower bounds for the split deliveryvehicle routing problem. Operations Research Letters,2010,38(4):302-306.
[52] Bompadre A, Dror M, Orlin JB. Improved bounds for vehicle routing solutions.Discrete Optimization,2006,3(4):299-316.
[53] Lee CG, Epelman MA, White CC, Bozer YA. A shortest path approach to themultiple-vehicle routing problem with split pick-ups. Transportation Research B,2006,40(4):265–284.
[54] Jin M, Liu K, Bowden RO. A two-stage algorithm with valid inequalities for thesplit delivery vehicle routing problem. International Journal of Production Economics,2007,105(1):228-242.
[55] Archetti C, Speranza MG, Hertz A. A tabu search algorithm for the split deliveryvehicle routing problem. Transportation Science,2006,40(1):64-73.
[56] Mota E, Campos V, Corberán A. A new metaheuristic for the vehicle routingproblem with split demands. Proceedings of the7th European conference onEvolutionary computation in combinatorial optimization. Berlin: Springer-Verlag,2007：121–129.
[57] Boudia M, Prins C, Reghioui M. An effective memetic algorithm with populationmanagement for the split-delivery vehicle routing problem. Proceedings of the4thinternational conference on Hybrid metaheuristics. Berlin: Springer-Verlag,2007:16–30.
[58] Archetti C, Savelsbergh MWP, Speranza MG. An optimization-based heuristic forthe split delivery vehicle routing problem. Transportation Science,2008,42(1):22-31.
[59] Chen S, Golden BL, Wasil E. The split delivery vehicle routing problem:applications, algorithms, test problems and computational results. Networks,2007,49(4)318–329.
[60] Archetti C, Savelsbergh MWP, Speranza MG. To split or not to split: that is thequestion. Transportation Research Part E: Logistics and Transportation Review,2008,40(1):114-123.
[61] Mullaseril PA, Dror M, Leung J. Split-delivery routing in livestock feeddistribution. Journal of the Operational Research Society,1997,48(2):107-116.
[62] Sierksma G, Tijssen GA. Routing helicopters for crew exchanges on off-shorelocations. Annals of Operations Research,1998,76(0):261-286.
[63]Archetti C, Speranza MG. Vehicle routing in the1-skip collection problem. Journalof the Operational Research Society,2004,55(7):717-727.
[64] Song S, Lee K, Kim G. A practical approach to solving a newspaper logisticsproblem using a digital map. Comput Ind Eng,2002,43(1-2):315–330.
[65] Min H. The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A,1989,23(5):377–386.
[66]唐国春.新的车辆路径问题.中国运筹学会第九届学术交流会论文集.Hongkong: Global-Link Informatics Limited，2008:269-277．
[67]杨亚璪，靳文舟，郝小妮，田晟.求解集送货可拆分车辆路径问题的启发式算法.华南理工大学学报（自然科学版）,2010,38(3):58-63.
[68]王晓东.计算机算法设计与分析（第3版）.北京:电子工业出版社,2007.
[69] Papadimitriou CH, Steiglitz K. Combinatorial optimization: algorithms andcomplexity. NewJersey: Prentice Hall,1982.
[70]张利昂.NP完全性理论介绍.计算机工程与应用，1984（5）:1-33.
[71] Gary MR, Johnson DS. Computers and Intractability: A Guide to the Theory ofNp-Completeness. San Francisco: W.H.Freeman and company,1979.
[72] Gerards AMH. Matching. Handbooks in Operations Research and ManagementScience. North-Holland, Amsterdam,1995.
[73] Tardos E. A strongly polynomial minimum cost circulation algorithm.Combinatorica.1985,5(3):247-255.
[74]宁爱兵.竞争决策算法及其在组合优化中的应用.上海理工大学博士学位论文,2005.
[75]熊小华.元胞竞争决策算法及其应用研究.上海理工大学博士学位论文,2011.
[76]宁爱兵，马良.度约束最小生成树（DCMST）的竞争决策算法.系统工程学报.2005,20(6):630-634.
[77] Desrosiers J, Soumis F, Desrochers M. Routing with time windows by columngeneration. Networks,1984,14(4):545-565.
[78] Solomon MM. Algorithm for the vehicle routing and scheduling problems withtime window constraints. Operations Research,1987,35(2):254-265.
[79] Olli Br ysy, Michel Gendreau.Vehicle routing problem with time windows, part I:route construction and local search algorithms. Transportation science,2005,39(1):104-118.
[80] Olli Br ysy, Michel Gendreau. Vehicle routing problem with time windows, partII: metaheuristics. Transportation science,2005,39(1):119-139.
[81] Angelelli E, Mansini R. The vehicle routing problem with time windows andsimultaneous pickup and delivery. Quantitative Approaches to Distribution Logisticsand Supply ChainManagement. Berlin: Springer-Verlag,2002:249-267.
[82]马庆国,孟丽君.基于混合算法的具有硬时间窗口约束的VRPSPD问题.西安电子科技大学学报,2009,19(2):41-46．
[83] Lai MY， Cao EB. An improved differential evolution algorithm for vehiclerouting problem with simultaneous pickups and deliveries and time windows.Engineering Applications of Artificial Intelligence,2010,23(2):188-195．
[84]殷佳林,蒋泰.基于蚁群算法求解带硬时间窗的VRPSDP.计算机系统应用，2009,(8):152-155．
[85] Chang MS, Chen SR, Hsueh CF. Real-time vehicle routing problem with timewindows and simultaneous delivey/pickup demands. Journal of the Eastern AsiaSociety，2003,5:2273-2286．
[86] Ho S C, Haugland D. A tabu search heuristic for the vehicle routing problem withtime windows and split deliveries. Computers&Operations Research.2004,31(12):1947-1964.
[87] Grotschel M, Holland O. Solution of large-scale travelling salesman problems.Mathematical Programming,1991,51(2):141-202.
[88] Padberg M, Rinaldi G. A branch-and-cut algorithm for the resolution of large-scalesymmetric traveling salesman problems. SIAM Review,1991,33(1):60-100.
[89] Mitchell, J.E. Branch-and-cut algorithms for combinatorial optimization problems.Handbook of Applied Optimization. New York: Oxford University Press,2002:65–77.
[90] Lysgaard J, Letchford AN, Eglese RW. A new branch-and-cut algorithm for thecapacitated vehicle routing problem. Mathematical Programming,2004,100(2):423–445.
[91] Lysgaard J. CVRPSEP: a package of separation routines for the capacitated vehiclerouting problem. Working Paper,2004,03-04, Department of Business Studies, AarhusSchool of Business, University of Aarhus, Danmark.
[92] Subramanian A, Uchoa E, Ochi LS. New lower bounds for the vehicle routingproblem with simultaneous pickup and delivery. Lecture Notes in Computer Science,2010,6049:276-287.
[93] Subramanian A, Uchoa E, Pessoa AA. Branch-and-cut with lazy separation for theVehicle Routing Problem with Simultaneous Pickup and Delivery. OperationsResearch Letters,2011,39(5):338-341.
[94] Cordier C, Marchand H, Laundy R, et al. bc-opt: A branch-and-cut code for mixedinteger programs. Mathematical Programming,1999,86(2):335-353.
[95]朱道立.大系统优化理论与应用.上海：上海交通大学出版社，1987.
[96] Wilhelm WE. A technical review of column generation in integer programming.Optimization and Engineering,2001,2(2):159-200.
[97] Dell'amico M, Righini G, Salani M. A branch-and-price approach to the vehiclerouting problem with simultaneous distribution and collection. Transportation Science,2006,40(2):235-247.
[98]李晨.带有协作机制的车辆路径问题的分支定价算法.南开大学硕士学位论文，2010.
[99] Nagy G, Salhi S. Heuristic algorithms for single and multiple depot vehiclerouting problems with pickups and deliveries. European Journal of OperationalResearch,2005,162(1):126–141.
[100] Bianchessi N, Righini G. Heuristic algorithms for the vehicle routing problemwith simultaneous pick-up and delivery. Computers&Operations Research,2007,34(2):578–594.
[101] Crispim J, Brandao J. Metaheuristics applied to mixed and simultaneousextensions of vehicle routing problems with backhauls. Journal of the OperationalResearch Society,2005,56(7):1296–302.
[102] Hansen P, Mladenovic N. Variable neighborhood search: principles andapplications. European Journal of Operational Research,2001,130(3):449–467.
[103] Ropke S, Pisinger D. A unified heuristic for vehicle routing problems withbackhauls. European Journal of Operational Research,2006,171(3):750–775.
[104] Wassan NA, Wassan AH, Nagy G. A reactive tabu search algorithm for thevehicle routing problem with simultaneous pickups and deliveries. Journal ofCombinatorial Optimization,2008,15(4):368–386.
[105] Chen JF, Wu TH. Vehicle routing problem with simultaneous deliveries andpickups. Journal of the Operational Research Society,2006,57(5):579–587.
[106] Zachariadis EE, Tarantilis CD, Kiranoudis CT. A hybrid metaheuristic algorithmfor the vehicle routing problem with simultaneous delivery and pick-up service. ExpertSystems with Applications,2009,36(2):1070–1081.
[107] Gribkovskaia I, Halskau, Laporte G, et al. General solutions to the singlevehicle routing problem with pickups and deliveries. European Journal of OperationalResearch,2007,180(2):568–584.
[108] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony ofcooperating agents. IEEE Transactions Systems, Man, and Cybernetics,1996,26(1):29-41.
[109] Bullnheimer B, Hartl RF, Strauss C. Applying the ant system to the vehiclerouting problem. Meta-heuristics: advances and trends in local search paradigms foroptimization. Boston: Kluwer Academic Publishers,1999:285–296.
[110] Wade A, Salhi S. An ant system algorithm for the vehicle routing problems withbackhauls. Proceedings of MIC2001Fourth Metaheuristics International Conference.2001:199–203.
[111] Wade A, Salhi, S. An ant system algorithm for the mixed vehicle routing problemwith backhauls. Metaheuristics: Computer Decision Making. New York: Kluwer,2003:699–719.
[112] Reimann M, Ulrich U. Comparing backhauling strategies in vehicle routingusing ant colony optimization. Central European Journal of Operations Research,2006,14(2):105–123.
[113] Gokce EI. A revised ant colony system approach to vehicle routing problems.Master thesis, Sabanci University, Istanbul, Turkey,2004.
[114] Gajpal Y, Abad P. An ant colony system (ACS) for vehicle routing problem withsimultaneous delivery and pickup. Computers&Operations Research,2009,36(12):3215–3223.
[115]张涛，田文馨，张钥杰，等.基于剩余装载能力的蚁群算法求解同时送取货车辆路径问题.控制理论与应用,2009,26(5):546-549.
[116] Kennedy J, Eberhart R. Particle swarm optimization. Proceedings of IEEEinternational conference on neural networks. Piscataway, IEEE Service Center,1995,4:1942-1948.
[117]纪震，廖惠连，吴青华.粒子群算法及应用.北京：科学出版社，2009.
[118] Ai TJ, Kachitvichyanukul V. A particle swarm optimization for the vehiclerouting problem with simultaneous pickup and delivery. Computers&OperationsResearch,2009,36(5):1693-1702.
[119] Zhang NZ, Sun GH, Wu Y H, et al. A modified particle swarm optimization forthe vehicle routing problem with simultaneous pickup and delivery. Proceedings of the7th Asian Control Conference. Piscataway, IEEE Service Center,2009:1679-1684.
[120] Goksal FP, Karaoglan I, Altiparmak F. A hybrid discrete particle swarmoptimization for vehicle routing problem with simultaneous pickup and delivery.Computers&Industrial Engineering, in press, available online20January2012.
[121] Vural AV. A GA based meta-heuristic for capacitated vehicle routing problemwith simultaneous pick-up and deliveries.Master’s thesis, Sabanci University, Istanbul,Turkey,2003.
[122]彭春林，梁春华，周泓.求解同时取货和送货车辆路径问题的改进遗传算法.系统仿真学报,2008,20(9):2266-2270.
[123] Zachariadis EE, Tarantilis CD, Kiranoudis CT. An adaptive memorymethodology for the vehicle routing problem with simultaneous pick-ups anddeliveries. European Journal of Operational Research,2010,202(2):401–411.
[124] Paessens H. The savings algorithm for the vehicle routing problem. EuropeanJournal of Operational Research,1988,34(3):336–344.