带时间窗车辆路径问题及其启发式算法研究
|
摘要
车辆路径问题是研究如何通过合理规划行驶路线来实现运输成本优化的一类优化调度问题,其相关理论和算法对于降低物流成本具有重要的应用价值,因此一直是运筹学和组合优化领域的研究热点。多年来车辆路径问题已衍生出众多研究分支,如开放式车辆路径问题、多站点车辆路径问题、装卸货车辆路径问题、带时间窗车辆路径问题和周期性车辆路径问题等,并取得了大量的研究成果,同时车辆路径问题也广泛应用于生产和生活的各个方面,如信件投递、货物配送、车辆调度等,产生了巨大的经济效益。
在实际生活中,常常存在这样一类车辆路径问题:用户对时间有较为严格的要求,他们希望在事先指定的时间区间内进行服务,因此在规划车辆的行驶路线时,不仅要考虑车辆的负载限制,还要同时考虑用户时间要求的满足。这一类问题可以抽象为带时间窗的车辆路径问题,其中用户指定的时间区间称为时间窗。由于时间窗约束的引进,带时间窗的车辆路径问题的求解更加困难,因此带时间窗的车辆路径问题一直是车辆路径问题中最重要的研究分支之一。本文对带时间窗问题及其扩展问题的建模与求解算法进行了研究,主要研究成果如下:
(1)提出了“最先过期用户优先”规则用于求解带时间窗问题及其扩展问题。带时间窗的车辆路径问题及其扩展问题已被证明是NP-Hard问题,因此通常采用启发式算法求取满意解。本文从研究基本的单时间窗、非时变问题入手,在分析多种常见算法的基础上提出了“最先过期用户优先”的路径构造规则用于问题求解,并进一步改进算法处理带时间窗问题的扩展问题,实验证明该算法在大部分情况下都具有更优的性能。
(2)建立了多时间窗的车辆路径问题的数学模型,并利用启发式算法进行求解。实际生活中如包裹派送等常常存在用户的时间窗不止一个的情形,目前关于这种多时间窗问题的研究极少,常见的单时间窗模型无法正确处理多时间窗问题,本文分析多时间窗问题的基本性质,引入“虚拟用户”的概念实现了多时间窗问题向单时间窗问题的转换,建立了多时间窗问题的车辆流模型,并提出了启发式求解算法。
(3)建立了时变的带时间窗车辆路径问题的数学模型,并利用启发式算法进行求解。基本的带时间窗问题将车辆行驶过程考虑成理想状态下的匀速过程,然而实际生活中车辆的行驶速度会随着不同时间段车流量的不同而不同,即速度时变的车辆路径问题。由于时变问题更能准确反映现实情况,目前对它的研究正引起越来越多学者的关注。本文首先将车辆速度定义为时变分段函数,由此将时变问题描述成为分段非时变问题,并基于时变分段函数建立了时变问题的车辆流模型,然后利用启发式算法对时变问题进行求解。
(4)引入模拟退火算法求解带时间窗问题的扩展问题。本文改进基本的模拟退火算法用于求解带时间窗问题及其扩展问题,并简化邻域构造技术以提高算法效率,实验表明改进的模拟退火算法能够有效地求解带时间窗问题及其扩展问题。
Vehicle Routing Problem is a class of optimization problems, of which the objective is to construct a set of feasible routes to reduce transportation costs. The correlative theories and methods have great application values for reducing the logistic cost, so they are always the hotspot of operations research and combinatorial optimization domains. In recent years, the vehicle routing problem has generated a lot of branches, such as open vehicle routing problem, multi-depot vehicle routing problem, pickup and delievery problem, vehicle routing problem with time window, periodic vehicle routing problem and so on, and many improvements have been achieved. While the vehicle routing problem has been widely applied to many aspects in real life and production, such as mail delievery, goods delievery and vehicles scheduling and so on, great benefit has been gained.
In real life there is a class of vehicle routing problems: the customers have strict limit to their service time, and they hope they can be served in appointed time intervals, so the capacity constraint and the time constraint will be considered simultaneously while constructing the routes. This class of problems is called Vehicle Routing Problem with Time Window, in which the time intervals are called time window. Since the time window is introduced, the vehicle routing problem with time window is harder to solve, so it is always one of the most important branches in vehicle routing problems. The models and methods about vehicle routing problem with time window and its extended problems are studied in this paper, the main contributions of this paper are summarized as follows:
(1) A rule called "First-expired-first-served" is proposed to solve the vehicle routing problem with time window and its extended problems. The vehicle routing problem with time window and its extended problems have been proved to be NP-Hard, and heuristic methods are usually used to gain satisfying solution. This paper studies the basic vehicle routing problem with single time window under time independent, analyzing many common algorithms and proposed a rule which is called first-expired-first-served. Then the corresponding heuristic algorithm is improved to solve the extended problems. Experimental results show that the algorithm has better performance in mostly conditions.
(2) A model about the vehicle routing problem with multiple time windows is built and the heuristic algorithms are used to solve it. In real life such as parcel delievery, the customers often have serval time windows. Now the correlative research is few and the model of single time window can not be used to handle the problems correctly. This paper studies the characters of vehicle routing problem with multiple time windows, introduces the "virtual customers" concept to transfer the problem to vehicle routing problem with single time window, then builds a vehicle flow model about vehicle routing problem with multiple time windows and proposes heuristic algorithms.
(3) The model about the vehicle routing problem with time window under time dependent is built and the heuristic algorithms are used to solve it. The basic vehicle routing problem with time window consider the speed as a constant, but in real life the speed is usually alterable along with the different time segments, which is called vehicle routing problem with time window under time dependent. Because the time-varied condition is closer to real condition, the correlative research has attracted more and more attention. This paper defines the speed as a time-piecewise function and builds the vehicle flow model of vehicle routing problem with time window under time dependent, and then uses the heuristic algorithms to solve the problem.
(4) The simulated annealing algorithm is introduced to solve the extended problems of the vehicle routing problem with time window. This paper mends the simulated annealing algorithm to solve the extended problems of the vehicle routing problem with time window, and simplifies the neighborhood to improve the efficiency. Experimental results show that the improved simulated annealing algorithm can solve the vehicle routing problem with time window and its extended problems efficiently.
在实际生活中,常常存在这样一类车辆路径问题:用户对时间有较为严格的要求,他们希望在事先指定的时间区间内进行服务,因此在规划车辆的行驶路线时,不仅要考虑车辆的负载限制,还要同时考虑用户时间要求的满足。这一类问题可以抽象为带时间窗的车辆路径问题,其中用户指定的时间区间称为时间窗。由于时间窗约束的引进,带时间窗的车辆路径问题的求解更加困难,因此带时间窗的车辆路径问题一直是车辆路径问题中最重要的研究分支之一。本文对带时间窗问题及其扩展问题的建模与求解算法进行了研究,主要研究成果如下:
(1)提出了“最先过期用户优先”规则用于求解带时间窗问题及其扩展问题。带时间窗的车辆路径问题及其扩展问题已被证明是NP-Hard问题,因此通常采用启发式算法求取满意解。本文从研究基本的单时间窗、非时变问题入手,在分析多种常见算法的基础上提出了“最先过期用户优先”的路径构造规则用于问题求解,并进一步改进算法处理带时间窗问题的扩展问题,实验证明该算法在大部分情况下都具有更优的性能。
(2)建立了多时间窗的车辆路径问题的数学模型,并利用启发式算法进行求解。实际生活中如包裹派送等常常存在用户的时间窗不止一个的情形,目前关于这种多时间窗问题的研究极少,常见的单时间窗模型无法正确处理多时间窗问题,本文分析多时间窗问题的基本性质,引入“虚拟用户”的概念实现了多时间窗问题向单时间窗问题的转换,建立了多时间窗问题的车辆流模型,并提出了启发式求解算法。
(3)建立了时变的带时间窗车辆路径问题的数学模型,并利用启发式算法进行求解。基本的带时间窗问题将车辆行驶过程考虑成理想状态下的匀速过程,然而实际生活中车辆的行驶速度会随着不同时间段车流量的不同而不同,即速度时变的车辆路径问题。由于时变问题更能准确反映现实情况,目前对它的研究正引起越来越多学者的关注。本文首先将车辆速度定义为时变分段函数,由此将时变问题描述成为分段非时变问题,并基于时变分段函数建立了时变问题的车辆流模型,然后利用启发式算法对时变问题进行求解。
(4)引入模拟退火算法求解带时间窗问题的扩展问题。本文改进基本的模拟退火算法用于求解带时间窗问题及其扩展问题,并简化邻域构造技术以提高算法效率,实验表明改进的模拟退火算法能够有效地求解带时间窗问题及其扩展问题。
Vehicle Routing Problem is a class of optimization problems, of which the objective is to construct a set of feasible routes to reduce transportation costs. The correlative theories and methods have great application values for reducing the logistic cost, so they are always the hotspot of operations research and combinatorial optimization domains. In recent years, the vehicle routing problem has generated a lot of branches, such as open vehicle routing problem, multi-depot vehicle routing problem, pickup and delievery problem, vehicle routing problem with time window, periodic vehicle routing problem and so on, and many improvements have been achieved. While the vehicle routing problem has been widely applied to many aspects in real life and production, such as mail delievery, goods delievery and vehicles scheduling and so on, great benefit has been gained.
In real life there is a class of vehicle routing problems: the customers have strict limit to their service time, and they hope they can be served in appointed time intervals, so the capacity constraint and the time constraint will be considered simultaneously while constructing the routes. This class of problems is called Vehicle Routing Problem with Time Window, in which the time intervals are called time window. Since the time window is introduced, the vehicle routing problem with time window is harder to solve, so it is always one of the most important branches in vehicle routing problems. The models and methods about vehicle routing problem with time window and its extended problems are studied in this paper, the main contributions of this paper are summarized as follows:
(1) A rule called "First-expired-first-served" is proposed to solve the vehicle routing problem with time window and its extended problems. The vehicle routing problem with time window and its extended problems have been proved to be NP-Hard, and heuristic methods are usually used to gain satisfying solution. This paper studies the basic vehicle routing problem with single time window under time independent, analyzing many common algorithms and proposed a rule which is called first-expired-first-served. Then the corresponding heuristic algorithm is improved to solve the extended problems. Experimental results show that the algorithm has better performance in mostly conditions.
(2) A model about the vehicle routing problem with multiple time windows is built and the heuristic algorithms are used to solve it. In real life such as parcel delievery, the customers often have serval time windows. Now the correlative research is few and the model of single time window can not be used to handle the problems correctly. This paper studies the characters of vehicle routing problem with multiple time windows, introduces the "virtual customers" concept to transfer the problem to vehicle routing problem with single time window, then builds a vehicle flow model about vehicle routing problem with multiple time windows and proposes heuristic algorithms.
(3) The model about the vehicle routing problem with time window under time dependent is built and the heuristic algorithms are used to solve it. The basic vehicle routing problem with time window consider the speed as a constant, but in real life the speed is usually alterable along with the different time segments, which is called vehicle routing problem with time window under time dependent. Because the time-varied condition is closer to real condition, the correlative research has attracted more and more attention. This paper defines the speed as a time-piecewise function and builds the vehicle flow model of vehicle routing problem with time window under time dependent, and then uses the heuristic algorithms to solve the problem.
(4) The simulated annealing algorithm is introduced to solve the extended problems of the vehicle routing problem with time window. This paper mends the simulated annealing algorithm to solve the extended problems of the vehicle routing problem with time window, and simplifies the neighborhood to improve the efficiency. Experimental results show that the improved simulated annealing algorithm can solve the vehicle routing problem with time window and its extended problems efficiently.
引文
[1]Lim A.,Rodrigues B.,Xu Z.Transportation procurement with seasonally varying shipper demand and volume guarantees[J].Operations Research,2008,56(3):758-771.
[2]Agarwal R.Ergun ǒ.Ship scheduling and network design for cargo routing in liner shipping[J].Transportation Science,2008,42(2):175-196.
[3]Bertazzi L.Analysis of direct shipping policies in an inventory-routing problem with discrete shipping times[J].Management Science,2008,54(4):748-762.
[4]Anily S.,Tzur M.Shipping multiple items by capacitated vehicles:an optimal dynamic programming approach[J].Transportation Science,2005,39(2):233-248.
[5]Chang T.S.,Nozick L.K.,Turnquist M.A.Multiobjective path finding in stochastic dynamic networks,with application to routing Hazardous materials shipments[J].Transportation Science,2005,39(3):383-399.
[6]Dumas J.,Soumis F.Passenger flow model for airline networks[J].Transportation Science,2008,42(2):197-207.
[7]Lan S.,Clarke J.P.,Barnhart C.Planning for robust airline operations:optimizing aircraft routings and flight departure times to minimize passenger disruptions[J].Transportation Science,2006,40(1):15-28.
[8]Yen J.W.,Birge J.R.A stochastic programming approach to the airline crew scheduling problem[J].Transportation Science,2006,40(1):3-14.
[9]Schaefer A.J.,Johnson E.L.,Kleywegt A.J.et al.Airline crew scheduling under uncertainty[J].Transportation Science,2005,39(3):340-348.
[10]Coslovich L.,Pesenti R.,Ukovich W.A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem[J].European Journal of Operational Research,2006,17:1605-1615.
[11]Diana M.,Dessouky M.M.A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows[J].Transportation Research Part B,2004,38:539-557.
[12]Cordeau J.F.,Laporte G.A tabu search heuristic for the static multi-vehicle dial-a-ride problem[J].Transportation Research Part B,2003,37:579-594.
[13] Kim B.I., Kim S., Sahoo S. Waste collection vehicle routing problem with time windows[J].Computers & Operations Research, 2006, 33:3624-3642.
[14] Tung D.V., Pinnoi A. Vehicle routing-scheduling for waste collection in Hanoi[J]. European Journal of Operational Research, 2000, 125:449-468.
[15] Perrier N., Langevin A., Amaya C.A. Vehicle routing for urban snow plowing operations[J].Transportation Science, 2008,42(1): 44-56.
[16] Syam S.S. A multiple server location-allocation model for service system design[J]. Computers& Operations Research, 2008, 35: 2248-2265.
[17] Campbell J.F., Ernst A.T., Krishnamoorthy M. Hub arc location problems: part I - introduction and results[J]. Management Science, 2005,51(10): 1540-1555.
[18] Campbell J.F., Ernst A.T., Krishnamoorthy M. Hub arc location problems: part II - formulations and optimal algorithms[J]. Management Science, 2005, 51(10): 1556-1571.
[19] Jepsen M., Petersen B., Spoorendonk S. et al. Subset-row inequalities applied to the vehicle-routing problem with time windows[J]. Operations Research, 2008, 56(2): 497-511.
[20] Repoussis P.P., Tarantilis C.D., Ioannou G. The open vehicle routing problem with time windows[J]. Journal of the Operational Research Society, 2007, 58: 355-367.
[21] Vis I.F.A., Koster R.B.M., Savelsbergh M.W.P. Minimum vehicle fleet size under time-window constraints at a container terminal[J]. Transportation Science, 2005, 39(2): 249-260.
[22] Bent R., Hentenryck P.V. A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows[J]. Transportation Science, 2004, 38(4): 515-530.
[23] Braysy O. A Reactive Variable Neighborhood Search for the Vehicle-Routing Problem with Time Windows[J]. Informs Journal on Computing, 2003,15(4): 347-368.
[24] Russell R.A. Hybrid Heuristics for the Vehicle Routing Problem with Time Windows[J].Transportation Science, 1995,29(2): 156-166.
[25] Alvarenga G.B., Mateus G.R., Tomi G. A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows[J]. Computers & Operations Research, 2007, 34:1561-1584.
[26] Chen Z.L., Xu H. Dynamic column generation for dynamic vehicle routing with time windows[J]. Transportation Science, 2006,40(1): 74-88.
[27] Bramel J. Levi D.S. Probabilistic analyses and practical algorithms for the vehicle routing problem with time windows[J]. Operations Research, 1996, 44(3): 501-509.
[28] Savelsbergh M.W.P. The Vehicle Routing Problem with Time Windows: Minimizing Route Duration[J]. ORSA Journal on Computing, 1992,4(2): 146-154.
[29] Kontoravdis G., Bard J.F. A GRASP for the Vehicle Routing Problem with Time Windows[J].ORSA Journal on Computing, 1995, 7(1): 10-23.
[30] Kolen A.W.J., Kan A.H.G.R., Trienekens H.W.J.M. Vehicle Routing with Time Windows[J].Operations Research, 1987, 35(2): 266-273.
[31] Amico M.D., Monaci ML, Pagani C. et al. Heuristic approaches for the fleet size and mix vehicle routing problem with time windows[J]. Transportation Science, 2007: 41(4): 516-526.
[32] Ioannou G., Kritikos M.N. A synthesis of assignment and heuristic solutions for vehicle routing with time windows[J]. Journal of the Operational Research Society, 2004, 55:2-11.
[33] Hong S.C., Park Y.B. A heuristic for bi-objective vehicle routing with time window constraints[J]. Int. J. Production Economics, 1999,62: 249-258.
[34] Durbin M., Hoffman K. The dance of the thirty-ton trucks: dispatching and scheduling in a dynamic environment[J]. Operations Research, 2008, 56(1): 3-19.
[35] Ozener O.O., Ergun O. Allocating costs in a collaborative transportation procurement network[J]. Transportation Science, 2008,42(2): 146-165.
[36] Cohn A., Root S., Wang A. et al. Integration of the load-matching and routing problem with equipment balancing for small package carriers[J]. Transportation Science, 2007,41(2):238-252.
[37] Listes O., Dekker R. A scenario aggregation-based approach for determining a robust airline fleet composition for dynamic capacity allocation[J]. Transportation Science, 2005,39(3):367-382.
[38] Archetti C., Speranza M.G., Savelsbergh M.W.P. An optimization-based heuristic for the split delivery vehicle routing problem[J]. Transportation Science, 2008, 42(1): 22-31.
[39] Mercier A. A theoretical comparison of feasibility cuts for the integrated aircraft-routing and crew-pairing problem[J]. Transportation Science, 2008,42(1): 87-104.
[40] Ergun O., Kuyzu G., Savelsbergh M. Reducing truckload transportation costs through collaboration[J]. Transportation Science, 2007, 41(2): 206-221.
[41] Babonneau F., Vial J.P. An efficient method to compute traffic assignment problems with elastic demands[J]. Transportation Science, 2008,42(2): 249-260.
[42] Duchenne E., Laporte G., Semet F. The Undirected m-Peripatetic Salesman Problem:Polyhedral Results and New Algorithms[J]. Operations Research, 2007, 55(5): 949-965.
[43] Lysgaard J. Reachability cuts for the vehicle routing problem with time windows[J]. European Journal of Operational Research,2006,175:210-223.
[44]Constantino M.,Martins I.,Borges J.G.A new mixed-integer programming model for harvest scheduling subject to maximum area restrictions[J].Operations Research,2008,56(3):542-551.
[45]Bramel J.,Levi D.S.On the effectiveness of set covering formulations for the vehicle routing problem with time windows[J].Operations Research,1997,45(2):295-301.
[46]Berger R.T.,Coullard C.R.,Daskin M.S.Location-routing problems with distance constraints[J].Transportation Science,2007,41(1):29-43.
[47]Erkut E.,Alp O.Integrated routing and scheduling of Hazmat trucks with stops en route[J].Transportation Science,2007,41(1):107-122
[48]Borndǒrfer R.,Grǒtschel M.,Pfetsch M.E.A column-generation approach to line planning in public transport[J].Transportation Science,2007,41(1):123-132.
[49]Chuah K.H.,Yingling J.C.Routing for a just-in-time supply pickup and delivery system[J].Transportation Science,2005,39(3):328-339.
[50]Azi N.,Gendreau M.,Potvin J.Y.An exact algorithm for a single-vehicle routing problem with time windows and multiple routes[J].European Journal of Operational Research,2007,178:755-766.
[51]Bienstock D.,Bramel J.,Levi D.S.A probabilistic analysis of tour partitioning heuristics for the capacitated vehicle routing[J].Mathematics of Operations Research,1993,184:786-802.
[52]杨珺,张敏,陈新.一类带服务半径的服务站截流选址-分配问题[J].系统工程理论与实践,2006,1:117-122.
[53]Berman O.,Huang R.The minisum multipurpose trip location problem on networks[J].Transportation Science,2007,41(4):500-515.
[54]Potvin J.Y.,Kervahut T.,Garcia B.L.et al.The Vehicle Routing Problem with Time Windows Part Ⅰ:Tabu Search[J].Informs Journal on Computing,1996,8(2):158-164.
[55]Brǎysy O.,Gendreau M.Vehicle Routing Problem with Time Windows,Part Ⅱ:Metaheuristics[J].Transportation Science,2005,39(1):119-139.
[56]Moghaddam R.T.,Safaei N.,Gholipour Y.A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length[J].Applied Mathematics and Computation,2006,176:445-454.
[57]郎茂祥.装卸混合车辆路径问题的模拟退火算法研究[J].2005,20(5):485-491.
[58]任传祥,张海,范跃祖.混合遗传_模拟退火算法在公交智能调度中的应用[J].系统仿真学报,2005,17(9):2075-2081.
[59]Dror M.,Laporte G.,Trudeau P.Vehicle Routing with Stochastic Demands-- Properties and Solutions Frameworks[J].Transportation Science,1989,23(3):166-176.
[60]Bertsimas D.J.A Vehicle Routing Problem with Stochastic Demand[J].Operations Research,1992,40(3):574-585.
[61]Secomandi N.Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands[J].Computers & Operations Research,2000,27:1201-1225.
[62]Yang W.H.,Mathur K.,Ballou R.H.Stochastic Vehicle Routing Problem with Restocking[J].Transportation Science,2000,34(1):99-112.
[63]Chan Y.,Carter W.B.,Burnes M.D.A multiple-depot,multiple-vehicle,location-routing problem with stochastically processed demands[J].Computers & Operations Research,2001,28:803-826.
[64]Hvattum L.M.,Lokketangen A.,Laporte G.Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic[J].Transportation Science,2006,40(4):421-438,
[65]Ak A.,Erera A.L.A paired-vehicle recourse strategy for the vehicle-routing problem with stochastic demands[J].Transportation Science,2007,41(2):222-237.
[66]Haugland D.,Ho S.C.,Laporte G.Designing delivery districts for the vehicle routing problem with stochastic demands[J].European Journal of Operational Research,2007,180:997-1910.
[67]Sherali H.D.,Zhu X.Two-stage fleet assignment model considering stochastic passenger demands[J].Operations Research,2008,56(2):383-399.
[68]Laporte G.,Louveaux F.V.,Hamme L.V.An Integer L-shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands[J].Operations Research,2002,50(3):415-423.
[69]Gendreau M.,Laporte G.,Séguin R.An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers[J].Transportation Science,1995,29(2):143-155.
[70]郭耀煌,钟小鹏.动态车辆路径问题排队模型分析[J].管理科学学报,2006,9(1):33-37.
[71]Kenyon A.S.,Morton D.P.Stochastic Vehicle Routing with Random Travel Times[J].Transportation Science,2003,37(1):69-82.
[72]Bertsimas D.J.,Ryzin G.V.A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane[J].Operations Research,1991,39(4):601-615.
[73]Laporte G.,Louveaux F.,Mercure H.The Vehicle Routing Problem with Stochastic Travel Times[J].Transportation Science,1992,26(3):161-170.
[74]Bertsimas D.J.,Ryzin G.V.Stochastic and dynamic vehicle routing in the Euclidean plane with multiple capacitated vehicles[J].Operations Research,1993,41(1):60-76.
[75]Bent R.W.,Hentenryck P.V.Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers[J].Operations Research,2004,52(6):977-987
[76]Sambola M.A.,Fernández E.,Laporte G.Heuristic and lower bound for a stochastic location-routing problem[J].European Journal of Operational Research,2007,179:940-955.
[77]Thomas B.W.Waiting strategies for anticipating service requests from known customer locations[J].Transportation Science,2007,41(3):319-331.
[78]Belenguer J.M.,Martinez M.C.,Mota E.A Lower Bound for the Split Delivery Vehicle Routing Problem[J].Operations Research,2000,48(5):801-810.
[79]Lee C.G.,Epelman M.A.,White C.C.et al.A shortest path approach to the multiple-vehicle routing problem with split pick-ups[J].Transportation Research Part B,2006,40:265-284.
[80]Archetti C.,Savelsbergh M.W.P.,Speranza M.G.Worst-case analysis for split delivery vehicle routing problems[J].Transportation Science,2006,40(2):226-234.
[81]Nowak M.,Ergun ǒ.,White C.C.Pickup and delivery with split loads[J].Transportation Science,2008,42(1):32-43.
[82]Ho S.C.,Haugland D.A Tabu Search heuristic for the vehicle routing problem with time windows and split deliveries[J].Computers & Operations Research,2004,31:1947-1964.
[83]Archetti C.,Speranza M.G.,Hertz A.A tabu search algorithm for the split delivery vehicle routing problem[J].Transportation Science,2006,40(1):64-73.
[84]宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的遗传算法[J].系统仿真学报,2005,17(11):2593-2597.
[85]Laporte G.,Nobert Y.,Taillefer S.Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems[J].Transportation Science,1988,22(3):161-172.
[86]Huisman D.,Freling R.,Wagelmans A.P.M.Multiple-depot integrated vehicle and crew scheduling[J].Transportation Science,2005,39(4):491-502.
[87]Hadjar A.,Marcotte O.,Soumis F.A branch-and-cut algorithm for the multiple depot vehicle scheduling problem[J].Operations Research,2006,54(1):130-149.
[88]Salhi S.,Sari M.A multi-level composite heuristic for the multi-depot vehicle fleet mix problem[J].European Journal of Operational Research,1997,103:95-112.
[89]Nagy G.,Salhi S.Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J].European Journal of Operational Research,2005,162:126-141.
[90]Dondo R.,Cerdá J.A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows[J].European Journal of Operational Research,2007,176:1478-1507.
[91]Wu T.H.,Low C.,Bai J.W.Heuristic solutions to multi-depot location-routing problems[J].Computers & Operations Research,2002,29:1393-1415.
[92]钟石泉,贺国光.多车场有时间窗的多车型车辆调度及其禁忌算法研究[J].运筹学学报,2005,9(4):67-73.
[93]吕军,冯博琴,李波.多约束条件车辆路径问题的二阶段遗传退火算法[J].西安交通大学学报,2005,39(12):1299-1302.
[94]秦固.基于蚁群优化的多物流配送中心选址算法[J].系统工程理论与实践,2006,4:120-124
[95]Crevier B.,Cordeau J.F.,Laporte G.The multi-depot vehicle routing problem with inter-depot routes[J].European Journal of Operational Research,2007,176:756-773.
[96]Li C.L.,Levi D.S.Worst-Case Analysis of Heuristics for Multidepot Capacitated Vehicle Routing Problems[J].ORSA Journal on Computing,1990,2(1):64-73.
[97]Brandāo J.A tabu search algorithm for the open vehicle routing problem[J].European Journal of Operational Research,2004,157:552-564.
[98]Tarantilis C.D.,Diakoulaki D.,Kiranoudis C.T.Combination of geographical information system and efficient routing algorithms for real life distribution operations[J].European Journal of Operational Research,2004,152:437-453.
[99]符卓.带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究[J].系统工程理论与实践,2004,3:123-128.
[100]Aksen D.,ǒzyurt Z.,Aras N.Open vehicle routing problem with driver nodes and time deadlines[J].Journal of the Operational Research Society,2007,58:1223-1234.
[101]Gendreau M.,Laporte G.,Musaraganyi C.et al.A tabu search heuristic for the heterogeneous fleet vehicle routing problem[J].Computers & Operations Research,1999,26:1153-1173.
[102]Lima C.M.R.R.,Goldbarg M.C.,Goldbarg E.F.G.A Memetic Algorithm for the Heterogeneous Fleet Vehicle Routing Problem[J].Electronic Notes in Discrete Mathematics,2004,18:171-176.
[103]Tarantilis C.D.,Kiranoudis C.T.,Vassiliadis V.S.A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem[J].European Journal of Operational Research,2004,152:148-158.
[104] Wu P., Hartman J.C., Wilson G.R. An integrated model and solution approach for fleet sizing with heterogeneous assets[J]. Transportation Science, 2005, 39(1): 87-103.
[105] Toth P., Vigo D. An Exact Algorithm for the Vehicle Routing Problem with Backhauls[J].Transportation Science, 1997, 31(4): 372-385.
[106] Mingozzi A., Giorgi S., Baldacci R. An Exact Method for the Vehicle Routing Problem with Backhauls[J]. Transportation Science, 1999,33(3): 315-329.
[107] Duhamel C, Potvin J.Y., Rousseau J.M. A Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows[J]. Transportation Science, 1997,31(1): 49-59.
[108] Brandao J. A new tabu search algorithm for the vehicle routing problem with backhauls[J].European Journal of Operational Research, 2006, 173: 540-555.
[109] Yang H., Ye M., Tang W.H.C. et al. A multiperiod dynamic model of taxi services with endogenous service intensity[J]. Operations Research, 2005, 53(3): 501-515.
[110] Francis P., Smilowitz K. Modeling techniques for periodic vehicle routing problems[J].Transportation Research Part B, 2006, 40: 872-884.
[111] Francis P., Smilowitz K., Tzur M. The period vehicle routing problem with service choice[J].Transportation Science, 2006, 40(4): 439-454.
[112] Gaudioso M., Paletta G. A Heuristic for the Periodic Vehicle Routing Problem[J].Transportation Science, 1992,26(2): 86-92.
[113] Baptista S., Oliveira R.C., Zuquete E. A period vehicle routing case study[J]. European Journal of Operational Research, 2002, 139:220-229.
[114] Mourgaya M., Vanderbeck F. Column generation based heuristic for tactical planning in multi-period vehicle routing[J]. European Journal of Operational Research, 2007, 183:1028-1041.
[115] Kallehauge B. Formulations and exact algorithms for the vehicle routing problem with time windows[J]. Computers & Operations Research, 2008, 35: 2307-2330.
[116] Tan K.C., Lee L.H., Zhu Q.L. et al. Heuristic methods for vehicle routing problem with time windows[J]. Artificial Intelligence in Engineering, 2001, 15: 281-295.
[117] Calvete H.I., Gale C, Oliveros M.J. et al. A goal programming approach to vehicle routing problems with soft time windows[J]. European Journal of Operational Research, 2007,177:1720-1733.
[118] Koskosidis Y.A., Powell W.B., Solomon M.M. An Optimization-Based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints[J]. Transportation Science, 1992, 26(2):69-85.
[119]Taillard E.,Badeau P.,Gendreau M.et al.A Tabu Search Heuristic for the Vehicle Routing Problem with Soft time Windows[J].Transportation Science,1997,31(2):170-186.
[120]Gendreau M.,Guertin F.,Potvin J.Y.et al.Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching[J].Transportation Science,1999,33(4):381-390.
[121]Hashimoto H.,Ibaraki T.,Imahori S.et al.The vehicle routing problem with flexible time windows and traveling times[J].Discrete Applied Mathematics,2006,154:2271-2290.
[122]Favaretto D.,Moretti E.,Pellegrini P.Ant colony system for a VRP with multiple time windows and multiple visits[J].Journal of Interdisciplinary Mathematics,2007,10(2):263-284.
[123]Tagmouti M.,Gendreau M.,Potvin J.Y.Arc routing problems with time-dependent service costs[J].European Journal of Operational Research,2007,181:30-39.
[124]Chen H.K.,Hsueh C.F.,Chang M.S.The real-time time-dependent vehicle routing problem[J].Transportation Research Part E,2006,42:383-408.
[125]Xiang Z.,Chu C.,Chen H.The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments[J].European Journal of Operational Research,2008,185:534-551.
[126]Donati A.V.,Montemanni R.,Casagrande N.et al.Time dependent vehicle routing problem with a multi ant colony system[J].European Journal of Operational Research,2008,185:1174-1191.
[127]Woensel T.V.,Kerbache L.,Peremans H.et al.Vehicle routing with dynamic travel times:A queueing approach[J].European Journal of Operational Research,2008,186:990-1007.
[128]Brǎysy O.,Gendreau M.Vehicle Routing Problem with Time Windows,Part Ⅰ:Search Algorithms[J].Transportation Science,2005,39(1):104-118
[129]Tan K.C.,Lee L.H.,Zhu Q.L.et al.Heuristic methods for vehicle routing problem with time windows[J].Artificial Intelligence in Engineering,2001,15:281-295.
[130]Ropke S.,Pisinger D.An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J].Transportation Science,2006,40(4):455-472.
[131]张丽艳,庞小红,夏蔚军等.带时间窗车辆路径问题的混合粒子群算法[J].上海交通大学学报,2006,40(11):1890-1894+1900.
[132]李宁,邹彤,孙德宝.带时间窗车辆路径问题的粒子群算法[J].系统工程理论与实践,2004.4:130-135.
[133]李全亮.免疫算法在带时间窗的车辆路径问题中的应用[J].系统工程理论与实践,2006,10:119-124
[134]Russell R.A.,Chiang W.C.Scatter search for the vehicle routing problem With time windows[J].European Journal of Operational Research,2006,169:606-622.
[135]Solomon M.M.Algorithms for vehicle routing and scheduling problems With time window constraints[J].Operation Research,1987,35(2):254-265.
[136]Gillett B.,Miller L.A heuristic algorithm for the vehicle dispatch problem[J].Operations Research,1974,22:340-349.
[2]Agarwal R.Ergun ǒ.Ship scheduling and network design for cargo routing in liner shipping[J].Transportation Science,2008,42(2):175-196.
[3]Bertazzi L.Analysis of direct shipping policies in an inventory-routing problem with discrete shipping times[J].Management Science,2008,54(4):748-762.
[4]Anily S.,Tzur M.Shipping multiple items by capacitated vehicles:an optimal dynamic programming approach[J].Transportation Science,2005,39(2):233-248.
[5]Chang T.S.,Nozick L.K.,Turnquist M.A.Multiobjective path finding in stochastic dynamic networks,with application to routing Hazardous materials shipments[J].Transportation Science,2005,39(3):383-399.
[6]Dumas J.,Soumis F.Passenger flow model for airline networks[J].Transportation Science,2008,42(2):197-207.
[7]Lan S.,Clarke J.P.,Barnhart C.Planning for robust airline operations:optimizing aircraft routings and flight departure times to minimize passenger disruptions[J].Transportation Science,2006,40(1):15-28.
[8]Yen J.W.,Birge J.R.A stochastic programming approach to the airline crew scheduling problem[J].Transportation Science,2006,40(1):3-14.
[9]Schaefer A.J.,Johnson E.L.,Kleywegt A.J.et al.Airline crew scheduling under uncertainty[J].Transportation Science,2005,39(3):340-348.
[10]Coslovich L.,Pesenti R.,Ukovich W.A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem[J].European Journal of Operational Research,2006,17:1605-1615.
[11]Diana M.,Dessouky M.M.A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows[J].Transportation Research Part B,2004,38:539-557.
[12]Cordeau J.F.,Laporte G.A tabu search heuristic for the static multi-vehicle dial-a-ride problem[J].Transportation Research Part B,2003,37:579-594.
[13] Kim B.I., Kim S., Sahoo S. Waste collection vehicle routing problem with time windows[J].Computers & Operations Research, 2006, 33:3624-3642.
[14] Tung D.V., Pinnoi A. Vehicle routing-scheduling for waste collection in Hanoi[J]. European Journal of Operational Research, 2000, 125:449-468.
[15] Perrier N., Langevin A., Amaya C.A. Vehicle routing for urban snow plowing operations[J].Transportation Science, 2008,42(1): 44-56.
[16] Syam S.S. A multiple server location-allocation model for service system design[J]. Computers& Operations Research, 2008, 35: 2248-2265.
[17] Campbell J.F., Ernst A.T., Krishnamoorthy M. Hub arc location problems: part I - introduction and results[J]. Management Science, 2005,51(10): 1540-1555.
[18] Campbell J.F., Ernst A.T., Krishnamoorthy M. Hub arc location problems: part II - formulations and optimal algorithms[J]. Management Science, 2005, 51(10): 1556-1571.
[19] Jepsen M., Petersen B., Spoorendonk S. et al. Subset-row inequalities applied to the vehicle-routing problem with time windows[J]. Operations Research, 2008, 56(2): 497-511.
[20] Repoussis P.P., Tarantilis C.D., Ioannou G. The open vehicle routing problem with time windows[J]. Journal of the Operational Research Society, 2007, 58: 355-367.
[21] Vis I.F.A., Koster R.B.M., Savelsbergh M.W.P. Minimum vehicle fleet size under time-window constraints at a container terminal[J]. Transportation Science, 2005, 39(2): 249-260.
[22] Bent R., Hentenryck P.V. A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows[J]. Transportation Science, 2004, 38(4): 515-530.
[23] Braysy O. A Reactive Variable Neighborhood Search for the Vehicle-Routing Problem with Time Windows[J]. Informs Journal on Computing, 2003,15(4): 347-368.
[24] Russell R.A. Hybrid Heuristics for the Vehicle Routing Problem with Time Windows[J].Transportation Science, 1995,29(2): 156-166.
[25] Alvarenga G.B., Mateus G.R., Tomi G. A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows[J]. Computers & Operations Research, 2007, 34:1561-1584.
[26] Chen Z.L., Xu H. Dynamic column generation for dynamic vehicle routing with time windows[J]. Transportation Science, 2006,40(1): 74-88.
[27] Bramel J. Levi D.S. Probabilistic analyses and practical algorithms for the vehicle routing problem with time windows[J]. Operations Research, 1996, 44(3): 501-509.
[28] Savelsbergh M.W.P. The Vehicle Routing Problem with Time Windows: Minimizing Route Duration[J]. ORSA Journal on Computing, 1992,4(2): 146-154.
[29] Kontoravdis G., Bard J.F. A GRASP for the Vehicle Routing Problem with Time Windows[J].ORSA Journal on Computing, 1995, 7(1): 10-23.
[30] Kolen A.W.J., Kan A.H.G.R., Trienekens H.W.J.M. Vehicle Routing with Time Windows[J].Operations Research, 1987, 35(2): 266-273.
[31] Amico M.D., Monaci ML, Pagani C. et al. Heuristic approaches for the fleet size and mix vehicle routing problem with time windows[J]. Transportation Science, 2007: 41(4): 516-526.
[32] Ioannou G., Kritikos M.N. A synthesis of assignment and heuristic solutions for vehicle routing with time windows[J]. Journal of the Operational Research Society, 2004, 55:2-11.
[33] Hong S.C., Park Y.B. A heuristic for bi-objective vehicle routing with time window constraints[J]. Int. J. Production Economics, 1999,62: 249-258.
[34] Durbin M., Hoffman K. The dance of the thirty-ton trucks: dispatching and scheduling in a dynamic environment[J]. Operations Research, 2008, 56(1): 3-19.
[35] Ozener O.O., Ergun O. Allocating costs in a collaborative transportation procurement network[J]. Transportation Science, 2008,42(2): 146-165.
[36] Cohn A., Root S., Wang A. et al. Integration of the load-matching and routing problem with equipment balancing for small package carriers[J]. Transportation Science, 2007,41(2):238-252.
[37] Listes O., Dekker R. A scenario aggregation-based approach for determining a robust airline fleet composition for dynamic capacity allocation[J]. Transportation Science, 2005,39(3):367-382.
[38] Archetti C., Speranza M.G., Savelsbergh M.W.P. An optimization-based heuristic for the split delivery vehicle routing problem[J]. Transportation Science, 2008, 42(1): 22-31.
[39] Mercier A. A theoretical comparison of feasibility cuts for the integrated aircraft-routing and crew-pairing problem[J]. Transportation Science, 2008,42(1): 87-104.
[40] Ergun O., Kuyzu G., Savelsbergh M. Reducing truckload transportation costs through collaboration[J]. Transportation Science, 2007, 41(2): 206-221.
[41] Babonneau F., Vial J.P. An efficient method to compute traffic assignment problems with elastic demands[J]. Transportation Science, 2008,42(2): 249-260.
[42] Duchenne E., Laporte G., Semet F. The Undirected m-Peripatetic Salesman Problem:Polyhedral Results and New Algorithms[J]. Operations Research, 2007, 55(5): 949-965.
[43] Lysgaard J. Reachability cuts for the vehicle routing problem with time windows[J]. European Journal of Operational Research,2006,175:210-223.
[44]Constantino M.,Martins I.,Borges J.G.A new mixed-integer programming model for harvest scheduling subject to maximum area restrictions[J].Operations Research,2008,56(3):542-551.
[45]Bramel J.,Levi D.S.On the effectiveness of set covering formulations for the vehicle routing problem with time windows[J].Operations Research,1997,45(2):295-301.
[46]Berger R.T.,Coullard C.R.,Daskin M.S.Location-routing problems with distance constraints[J].Transportation Science,2007,41(1):29-43.
[47]Erkut E.,Alp O.Integrated routing and scheduling of Hazmat trucks with stops en route[J].Transportation Science,2007,41(1):107-122
[48]Borndǒrfer R.,Grǒtschel M.,Pfetsch M.E.A column-generation approach to line planning in public transport[J].Transportation Science,2007,41(1):123-132.
[49]Chuah K.H.,Yingling J.C.Routing for a just-in-time supply pickup and delivery system[J].Transportation Science,2005,39(3):328-339.
[50]Azi N.,Gendreau M.,Potvin J.Y.An exact algorithm for a single-vehicle routing problem with time windows and multiple routes[J].European Journal of Operational Research,2007,178:755-766.
[51]Bienstock D.,Bramel J.,Levi D.S.A probabilistic analysis of tour partitioning heuristics for the capacitated vehicle routing[J].Mathematics of Operations Research,1993,184:786-802.
[52]杨珺,张敏,陈新.一类带服务半径的服务站截流选址-分配问题[J].系统工程理论与实践,2006,1:117-122.
[53]Berman O.,Huang R.The minisum multipurpose trip location problem on networks[J].Transportation Science,2007,41(4):500-515.
[54]Potvin J.Y.,Kervahut T.,Garcia B.L.et al.The Vehicle Routing Problem with Time Windows Part Ⅰ:Tabu Search[J].Informs Journal on Computing,1996,8(2):158-164.
[55]Brǎysy O.,Gendreau M.Vehicle Routing Problem with Time Windows,Part Ⅱ:Metaheuristics[J].Transportation Science,2005,39(1):119-139.
[56]Moghaddam R.T.,Safaei N.,Gholipour Y.A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length[J].Applied Mathematics and Computation,2006,176:445-454.
[57]郎茂祥.装卸混合车辆路径问题的模拟退火算法研究[J].2005,20(5):485-491.
[58]任传祥,张海,范跃祖.混合遗传_模拟退火算法在公交智能调度中的应用[J].系统仿真学报,2005,17(9):2075-2081.
[59]Dror M.,Laporte G.,Trudeau P.Vehicle Routing with Stochastic Demands-- Properties and Solutions Frameworks[J].Transportation Science,1989,23(3):166-176.
[60]Bertsimas D.J.A Vehicle Routing Problem with Stochastic Demand[J].Operations Research,1992,40(3):574-585.
[61]Secomandi N.Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands[J].Computers & Operations Research,2000,27:1201-1225.
[62]Yang W.H.,Mathur K.,Ballou R.H.Stochastic Vehicle Routing Problem with Restocking[J].Transportation Science,2000,34(1):99-112.
[63]Chan Y.,Carter W.B.,Burnes M.D.A multiple-depot,multiple-vehicle,location-routing problem with stochastically processed demands[J].Computers & Operations Research,2001,28:803-826.
[64]Hvattum L.M.,Lokketangen A.,Laporte G.Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic[J].Transportation Science,2006,40(4):421-438,
[65]Ak A.,Erera A.L.A paired-vehicle recourse strategy for the vehicle-routing problem with stochastic demands[J].Transportation Science,2007,41(2):222-237.
[66]Haugland D.,Ho S.C.,Laporte G.Designing delivery districts for the vehicle routing problem with stochastic demands[J].European Journal of Operational Research,2007,180:997-1910.
[67]Sherali H.D.,Zhu X.Two-stage fleet assignment model considering stochastic passenger demands[J].Operations Research,2008,56(2):383-399.
[68]Laporte G.,Louveaux F.V.,Hamme L.V.An Integer L-shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands[J].Operations Research,2002,50(3):415-423.
[69]Gendreau M.,Laporte G.,Séguin R.An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers[J].Transportation Science,1995,29(2):143-155.
[70]郭耀煌,钟小鹏.动态车辆路径问题排队模型分析[J].管理科学学报,2006,9(1):33-37.
[71]Kenyon A.S.,Morton D.P.Stochastic Vehicle Routing with Random Travel Times[J].Transportation Science,2003,37(1):69-82.
[72]Bertsimas D.J.,Ryzin G.V.A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane[J].Operations Research,1991,39(4):601-615.
[73]Laporte G.,Louveaux F.,Mercure H.The Vehicle Routing Problem with Stochastic Travel Times[J].Transportation Science,1992,26(3):161-170.
[74]Bertsimas D.J.,Ryzin G.V.Stochastic and dynamic vehicle routing in the Euclidean plane with multiple capacitated vehicles[J].Operations Research,1993,41(1):60-76.
[75]Bent R.W.,Hentenryck P.V.Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers[J].Operations Research,2004,52(6):977-987
[76]Sambola M.A.,Fernández E.,Laporte G.Heuristic and lower bound for a stochastic location-routing problem[J].European Journal of Operational Research,2007,179:940-955.
[77]Thomas B.W.Waiting strategies for anticipating service requests from known customer locations[J].Transportation Science,2007,41(3):319-331.
[78]Belenguer J.M.,Martinez M.C.,Mota E.A Lower Bound for the Split Delivery Vehicle Routing Problem[J].Operations Research,2000,48(5):801-810.
[79]Lee C.G.,Epelman M.A.,White C.C.et al.A shortest path approach to the multiple-vehicle routing problem with split pick-ups[J].Transportation Research Part B,2006,40:265-284.
[80]Archetti C.,Savelsbergh M.W.P.,Speranza M.G.Worst-case analysis for split delivery vehicle routing problems[J].Transportation Science,2006,40(2):226-234.
[81]Nowak M.,Ergun ǒ.,White C.C.Pickup and delivery with split loads[J].Transportation Science,2008,42(1):32-43.
[82]Ho S.C.,Haugland D.A Tabu Search heuristic for the vehicle routing problem with time windows and split deliveries[J].Computers & Operations Research,2004,31:1947-1964.
[83]Archetti C.,Speranza M.G.,Hertz A.A tabu search algorithm for the split delivery vehicle routing problem[J].Transportation Science,2006,40(1):64-73.
[84]宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的遗传算法[J].系统仿真学报,2005,17(11):2593-2597.
[85]Laporte G.,Nobert Y.,Taillefer S.Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems[J].Transportation Science,1988,22(3):161-172.
[86]Huisman D.,Freling R.,Wagelmans A.P.M.Multiple-depot integrated vehicle and crew scheduling[J].Transportation Science,2005,39(4):491-502.
[87]Hadjar A.,Marcotte O.,Soumis F.A branch-and-cut algorithm for the multiple depot vehicle scheduling problem[J].Operations Research,2006,54(1):130-149.
[88]Salhi S.,Sari M.A multi-level composite heuristic for the multi-depot vehicle fleet mix problem[J].European Journal of Operational Research,1997,103:95-112.
[89]Nagy G.,Salhi S.Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J].European Journal of Operational Research,2005,162:126-141.
[90]Dondo R.,Cerdá J.A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows[J].European Journal of Operational Research,2007,176:1478-1507.
[91]Wu T.H.,Low C.,Bai J.W.Heuristic solutions to multi-depot location-routing problems[J].Computers & Operations Research,2002,29:1393-1415.
[92]钟石泉,贺国光.多车场有时间窗的多车型车辆调度及其禁忌算法研究[J].运筹学学报,2005,9(4):67-73.
[93]吕军,冯博琴,李波.多约束条件车辆路径问题的二阶段遗传退火算法[J].西安交通大学学报,2005,39(12):1299-1302.
[94]秦固.基于蚁群优化的多物流配送中心选址算法[J].系统工程理论与实践,2006,4:120-124
[95]Crevier B.,Cordeau J.F.,Laporte G.The multi-depot vehicle routing problem with inter-depot routes[J].European Journal of Operational Research,2007,176:756-773.
[96]Li C.L.,Levi D.S.Worst-Case Analysis of Heuristics for Multidepot Capacitated Vehicle Routing Problems[J].ORSA Journal on Computing,1990,2(1):64-73.
[97]Brandāo J.A tabu search algorithm for the open vehicle routing problem[J].European Journal of Operational Research,2004,157:552-564.
[98]Tarantilis C.D.,Diakoulaki D.,Kiranoudis C.T.Combination of geographical information system and efficient routing algorithms for real life distribution operations[J].European Journal of Operational Research,2004,152:437-453.
[99]符卓.带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究[J].系统工程理论与实践,2004,3:123-128.
[100]Aksen D.,ǒzyurt Z.,Aras N.Open vehicle routing problem with driver nodes and time deadlines[J].Journal of the Operational Research Society,2007,58:1223-1234.
[101]Gendreau M.,Laporte G.,Musaraganyi C.et al.A tabu search heuristic for the heterogeneous fleet vehicle routing problem[J].Computers & Operations Research,1999,26:1153-1173.
[102]Lima C.M.R.R.,Goldbarg M.C.,Goldbarg E.F.G.A Memetic Algorithm for the Heterogeneous Fleet Vehicle Routing Problem[J].Electronic Notes in Discrete Mathematics,2004,18:171-176.
[103]Tarantilis C.D.,Kiranoudis C.T.,Vassiliadis V.S.A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem[J].European Journal of Operational Research,2004,152:148-158.
[104] Wu P., Hartman J.C., Wilson G.R. An integrated model and solution approach for fleet sizing with heterogeneous assets[J]. Transportation Science, 2005, 39(1): 87-103.
[105] Toth P., Vigo D. An Exact Algorithm for the Vehicle Routing Problem with Backhauls[J].Transportation Science, 1997, 31(4): 372-385.
[106] Mingozzi A., Giorgi S., Baldacci R. An Exact Method for the Vehicle Routing Problem with Backhauls[J]. Transportation Science, 1999,33(3): 315-329.
[107] Duhamel C, Potvin J.Y., Rousseau J.M. A Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows[J]. Transportation Science, 1997,31(1): 49-59.
[108] Brandao J. A new tabu search algorithm for the vehicle routing problem with backhauls[J].European Journal of Operational Research, 2006, 173: 540-555.
[109] Yang H., Ye M., Tang W.H.C. et al. A multiperiod dynamic model of taxi services with endogenous service intensity[J]. Operations Research, 2005, 53(3): 501-515.
[110] Francis P., Smilowitz K. Modeling techniques for periodic vehicle routing problems[J].Transportation Research Part B, 2006, 40: 872-884.
[111] Francis P., Smilowitz K., Tzur M. The period vehicle routing problem with service choice[J].Transportation Science, 2006, 40(4): 439-454.
[112] Gaudioso M., Paletta G. A Heuristic for the Periodic Vehicle Routing Problem[J].Transportation Science, 1992,26(2): 86-92.
[113] Baptista S., Oliveira R.C., Zuquete E. A period vehicle routing case study[J]. European Journal of Operational Research, 2002, 139:220-229.
[114] Mourgaya M., Vanderbeck F. Column generation based heuristic for tactical planning in multi-period vehicle routing[J]. European Journal of Operational Research, 2007, 183:1028-1041.
[115] Kallehauge B. Formulations and exact algorithms for the vehicle routing problem with time windows[J]. Computers & Operations Research, 2008, 35: 2307-2330.
[116] Tan K.C., Lee L.H., Zhu Q.L. et al. Heuristic methods for vehicle routing problem with time windows[J]. Artificial Intelligence in Engineering, 2001, 15: 281-295.
[117] Calvete H.I., Gale C, Oliveros M.J. et al. A goal programming approach to vehicle routing problems with soft time windows[J]. European Journal of Operational Research, 2007,177:1720-1733.
[118] Koskosidis Y.A., Powell W.B., Solomon M.M. An Optimization-Based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints[J]. Transportation Science, 1992, 26(2):69-85.
[119]Taillard E.,Badeau P.,Gendreau M.et al.A Tabu Search Heuristic for the Vehicle Routing Problem with Soft time Windows[J].Transportation Science,1997,31(2):170-186.
[120]Gendreau M.,Guertin F.,Potvin J.Y.et al.Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching[J].Transportation Science,1999,33(4):381-390.
[121]Hashimoto H.,Ibaraki T.,Imahori S.et al.The vehicle routing problem with flexible time windows and traveling times[J].Discrete Applied Mathematics,2006,154:2271-2290.
[122]Favaretto D.,Moretti E.,Pellegrini P.Ant colony system for a VRP with multiple time windows and multiple visits[J].Journal of Interdisciplinary Mathematics,2007,10(2):263-284.
[123]Tagmouti M.,Gendreau M.,Potvin J.Y.Arc routing problems with time-dependent service costs[J].European Journal of Operational Research,2007,181:30-39.
[124]Chen H.K.,Hsueh C.F.,Chang M.S.The real-time time-dependent vehicle routing problem[J].Transportation Research Part E,2006,42:383-408.
[125]Xiang Z.,Chu C.,Chen H.The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments[J].European Journal of Operational Research,2008,185:534-551.
[126]Donati A.V.,Montemanni R.,Casagrande N.et al.Time dependent vehicle routing problem with a multi ant colony system[J].European Journal of Operational Research,2008,185:1174-1191.
[127]Woensel T.V.,Kerbache L.,Peremans H.et al.Vehicle routing with dynamic travel times:A queueing approach[J].European Journal of Operational Research,2008,186:990-1007.
[128]Brǎysy O.,Gendreau M.Vehicle Routing Problem with Time Windows,Part Ⅰ:Search Algorithms[J].Transportation Science,2005,39(1):104-118
[129]Tan K.C.,Lee L.H.,Zhu Q.L.et al.Heuristic methods for vehicle routing problem with time windows[J].Artificial Intelligence in Engineering,2001,15:281-295.
[130]Ropke S.,Pisinger D.An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J].Transportation Science,2006,40(4):455-472.
[131]张丽艳,庞小红,夏蔚军等.带时间窗车辆路径问题的混合粒子群算法[J].上海交通大学学报,2006,40(11):1890-1894+1900.
[132]李宁,邹彤,孙德宝.带时间窗车辆路径问题的粒子群算法[J].系统工程理论与实践,2004.4:130-135.
[133]李全亮.免疫算法在带时间窗的车辆路径问题中的应用[J].系统工程理论与实践,2006,10:119-124
[134]Russell R.A.,Chiang W.C.Scatter search for the vehicle routing problem With time windows[J].European Journal of Operational Research,2006,169:606-622.
[135]Solomon M.M.Algorithms for vehicle routing and scheduling problems With time window constraints[J].Operation Research,1987,35(2):254-265.
[136]Gillett B.,Miller L.A heuristic algorithm for the vehicle dispatch problem[J].Operations Research,1974,22:340-349.