More Web Proxy on the site http://driver.im/

research-article

Testing local search move operators on the vehicle routing problem with split deliveries and time windows

Authors:

Marcus E. McNabb,

Jeffery D. Weir,

Raymond R. Hill,

Shane N. HallAuthors Info & Claims

Computers and Operations Research, Volume 56, Issue C

Pages 93 - 109

https://doi.org/10.1016/j.cor.2014.11.007

Published: 01 April 2015 Publication History

Abstract

The vehicle routing problem (VRP) is an important transportation problem. The literature addresses several extensions of this problem, including variants having delivery time windows associated with customers and variants allowing split deliveries to customers. The problem extension including both of these variations has received less attention in the literature. This research effort sheds further light on this problem. Specifically, this paper analyzes the effects of combinations of local search (LS) move operators commonly used on the VRP and its variants. We find when paired with a MAX-MIN Ant System constructive heuristic, Or-opt or 2-opt* appear to be the ideal LS operators to employ on the VRP with split deliveries and time windows with Or-opt finding higher quality solutions and 2-opt* requiring less run time.

References

[1]

G. Laporte, What you should know about the vehicle routing problem, Nav Res Logist, 54 (2007) 811-819.

[2]

C. Archetti, M.W. Savelsbergh, M.G. Speranza, To split or not to split: that is the question, Transp Res Part E, 44 (2008) 114-123.

[3]

M. Nowak, O. Ergun, C.C.I. White, Pickup and delivery with split loads, Transp Sci, 42 (2008) 32-43.

Digital Library

[4]

M. Nowak, O. Ergun, C.C.I. White, An empirical study on the benefit of split loads with the pickup and delivery problem, Eur J Oper Res, 198 (2008) 734-740.

[5]

G. Nagy, N.A. Wassan, M.G. Speranza, C. Archetti, The vehicle routing problem with divisible deliveries and pickups, Transp Sci (2014) 1-24.

[6]

McNabb ME, IV. Examining the effects of construction heuristics and problem structure on solution quality of the vehicle routing problem with split deliveries and time windows. In: Exploring heuristics for the vehicle routing problem with split deliveries and time windows. Wright Patterson AFB, OH: Air Force Institute of Technology; 2014. p. 65-90.

[7]

C. Archetti, M. Speranza, Vehicle routing problems with split deliveries, Int Trans Oper Res, 19 (2012) 3-22.

[8]

D. Feillet, P. Dejax, M. Gendreau, C. Gueguen, Vehicle routing with time windows and split deliveries, Laboratoire d'Informatique d'Avignon, Universite d'Avignon, Avignon, France, 2002.

[9]

P. Belfiore, H. Tsugunobu, Y. Yoshizaki, Scatter search for vehicle routing problem with time windows and split deliveries, in: Vehicle routing problem, I-Tech, Vienna, 2008, pp. 142.

[10]

P. Frizzell, J. Giffin, The split delivery vehicle scheduling problem with time windows and grid network distances, Comput Oper Res, 22 (1995) 655-667.

Digital Library

[11]

S. Ho, D. Haugland, A tabu search heuristic for the vehicle routing problem with time windows and split deliveries, Comput Oper Res, 31 (2004) 1947-1964.

[12]

G.G. Campos, H.T.Y. Yoshizaki, P.P. Belfiore, Genetic algorithms and parallel computing for the vehicle routing problem with time windows and split deliveries, Manag Prod, 13 (2006) 271-281.

[13]

M. Dror, P. Trudeau, Savings by split delivery routing, Transp Sci, 23 (1989) 141-145.

Digital Library

[14]

R.E. Aleman, X. Zhang, R.R. Hill, An adaptive memory algorithm for the split delivery routing problem, J Heuristics, 16 (2010) 441-473.

Digital Library

[15]

U. Derigs, B. Li, U. Vogel, Local search-based metaheuristics for the split delivery vehicle routing problem, J Oper Res Soc, 61 (2010) 1356-1364.

[16]

O. Braysy, M. Gendreau, Vehicle routing problem, Part I: route construction and local search algorithms, Transp Sci, 39 (2005) 104-118.

Digital Library

[17]

Xia L, Chao Y, Xia L. Optimization of vehicle routing problem based on max-min ant system with parameter adaptation. In: Proceedings of the seventh international conference on computational intelligence and security, Hainan; 2011.

[18]

X. Zhang, J.-Q. Wang, Hybrid ant algorithm and applications for vehicle routing problem, Phys Proc, 25 (2012) 1892-1899.

[19]

B. Yu, Z.-Z. Yang, B. Yao, An improved ant colony optimization for vehicle routing problem, Eur J Oper Res, 196 (2009) 171-176.

[20]

L.M. Gambardella, E. Taillard, G. Agazzi, MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows, 1999.

[21]

Q. Ding, X. Hu, L. Sun, Y. Wang, An improved ant colony optimization and its application to vehicle routing problem with time windows, Neurocomputing, 98 (2012) 101-107.

Digital Library

[22]

S. Sodsoon, P. Changyom, Max-Min Ant System (MMAS) for vehicle routing problem with time windows, KKU Eng J, 38 (2011) 313-323.

[23]

J. Kytojoki, T. Nuortio, O. Braysy, M. Gendreau, An efficient variable neighborhood search heuristic for very large scale vehicle routing problems, Comput Oper Res, 34 (2007) 2743-2757.

Digital Library

[24]

T. Stutzle, Local search algorithms for combinatorial problems: analysis, improvements, and new applications, Technical University of Darmstadt, 1998.

[25]

A. Van Breedam, An analysis of the behavior of heuristics for the vehicle routing Problem for a selection of problems with vehicle-related, customer-related, and time-related constraints, University of Antwerp, Antwerp, Belgium, 1994.

[26]

J.E. Bell, P.R. McMullen, Ant colony optimization techniques for the vehicle routing problem, Adv Eng Inf, 18 (2004) 41-48.

[27]

N.A. El-Sherbeny, Vehicle routing with time windows: an overview of exact, heuristic and metaheuristic methods, J King Saud Univ, 22 (2010) 123-131.

[28]

M. Dorigo, Optimization, learning, and natural algorithms, Politecnico di Milano, Milan, Italy, 1992.

[29]

M. Dorigo, T. Stutzle, Ant colony optimization: overview and recent advances, Springer, US, 2010.

[30]

Stutzle T, Hoos H. MAX-MIN ant system and local search for the traveling salesman problem. In: Proceedings of the IEEE international conference on evolutionary computation; 1997.

[31]

T. Stutzle, H.H. Hoos, MAX-MIN ant system, Future Gener Comput Syst, 16 (2000) 889-914.

Digital Library

[32]

T. Stutzle, M. Dorigo, a short convergence proof for a class of ant colony optimization algorithms, IEEE Trans Evol Comput, 6 (2002) 358-365.

Digital Library

[33]

S. Mazzeo, I. Loiseau, An ant colony algorithm for the capacitated vehicle routing, Electron Notes Discret Math, 18 (2004) 181-186.

[34]

Wang G-S, Yu Y-X. An improved ant colony algorithm for VRP problem. In: Proceedings of the third international symposium on intelligent information technology and security informatics, Jinggangshan; 2010.

Digital Library

[35]

P. Pelligrini, D. Favaretto, E. Moretti, On MAX-MIN ant system's parameters, in: Ant colony and swarm intelligence, Springer, Heidelberg, 2006, pp. 203-214.

[36]

M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper Res, 35 (1987) 254-265.

Digital Library

[37]

M. Boudia, C. Prins, M. Reghioui, An effective memetic algorithm with population management for the split delivery vehicle routing problem, in: Hybrid metaheuristics, lecture notes in computer science, 4771, Springer, Berlin, 2007, pp. 16-30.

[38]

E. Mota, V. Campos, A. Corberan, A new metaheuristic for the vehicle routing problem with split demands, Springer, Berlin, 2007.

[39]

J.H.I. Wilck, T.M. Cavalier, A construction heuristic for the split delivery vehicle routing problem, Am J Oper Res, 2 (2012) 153-162.

[40]

R.O. Duda, P.E. Hart, D.G. Stork, Pattern classification, Wiley-Interscience, New York, 2001.

[41]

MathWorks, "Hierarchical Clustering," Online}. Available: {http://www.mathworks.com/help/stats/hierarchical-clustering.html}; 2013 accessed 21.11.13}.

[42]

C.W. Dunnett, A multiple comparison procedure for comparing several treatments with a control, J Am Stat Assoc, 50 (1955) 1096-1121.

[43]

Tongarlak MH, Ankenman BE, Nelson BL. Relative Error Stochastic Kriging. In: Proceedings of the Winter Simulation Conference; 2011.

Cited By

Huang MLiu MKuang H(2024)Vehicle routing problem for fresh products distribution considering customer satisfaction through adaptive large neighborhood searchComputers and Industrial Engineering10.1016/j.cie.2024.110022190:COnline publication date: 9-Jul-2024
https://dl.acm.org/doi/10.1016/j.cie.2024.110022
Cura T(2023)Hybridizing local searching with genetic algorithms for the job sequencing and tool switching problem with non-identical parallel machinesExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.119908223:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.eswa.2023.119908
Wu YZhou MZhang DLi S(2022)A Biobjective Vehicle Routing Problem with Stochastic Demand and Split DeliveriesScientific Programming10.1155/2022/27902582022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/2790258
Show More Cited By

Testing local search move operators on the vehicle routing problem with split deliveries and time windows
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries

Vehicle routing problem with simultaneous and mixed pickups and deliveries have been addressed.An adaptive local search algorithm is proposed to solve the problems.The proposed approach generates high-quality solutions to the benchmark instances in ...
A parallel iterated tabu search heuristic for vehicle routing problems

This paper introduces a parallel iterated tabu search heuristic for solving four different routing problems: the classical vehicle routing problem (VRP), the periodic VRP, the multi-depot VRP, and the site-dependent VRP. In addition, it is applicable to ...
A Set-Partitioning-Based Heuristic for the Vehicle Routing Problem

<P>We develop a generic tabu search heuristic for solving the well-known vehicle routing problem. This algorithm explores the advantages of simple local search and improvement heuristics as well as a complex meta-heuristic. The solutions generated by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Operations Research

Computers and Operations Research Volume 56, Issue C

April 2015

151 pages

ISSN:0305-0548

Issue’s Table of Contents

Publisher

Elsevier Science Ltd.

United Kingdom

Publication History

Published: 01 April 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang MLiu MKuang H(2024)Vehicle routing problem for fresh products distribution considering customer satisfaction through adaptive large neighborhood searchComputers and Industrial Engineering10.1016/j.cie.2024.110022190:COnline publication date: 9-Jul-2024
https://dl.acm.org/doi/10.1016/j.cie.2024.110022
Cura T(2023)Hybridizing local searching with genetic algorithms for the job sequencing and tool switching problem with non-identical parallel machinesExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.119908223:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.eswa.2023.119908
Wu YZhou MZhang DLi S(2022)A Biobjective Vehicle Routing Problem with Stochastic Demand and Split DeliveriesScientific Programming10.1155/2022/27902582022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/2790258
Elshaer RAwad H(2022)A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variantsComputers and Industrial Engineering10.1016/j.cie.2019.106242140:COnline publication date: 21-Apr-2022
https://dl.acm.org/doi/10.1016/j.cie.2019.106242
Ji BZhou SYu SWu G(2021)An enhanced neighborhood search algorithm for solving the split delivery vehicle routing problem with two-dimensional loading constraintsComputers and Industrial Engineering10.1016/j.cie.2021.107720162:COnline publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1016/j.cie.2021.107720
Xu XZheng YYu L(2018)A bi-level optimization model of LRP in collaborative logistics network considered backhaul no-load costSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-018-3056-622:16(5385-5393)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1007/s00500-018-3056-6
(2017)Examining the effects of construction heuristics and problem structure on solution quality of the vehicle routing problem with split deliveries and time windowsInternational Journal of Metaheuristics10.1504/IJMHEUR.2017.0851266:3(234-256)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1504/IJMHEUR.2017.085126
Polat O(2017)A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickupsComputers and Operations Research10.1016/j.cor.2017.03.00985:C(71-86)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1016/j.cor.2017.03.009
Braekers KRamaekers KVan Nieuwenhuyse I(2016)The vehicle routing problemComputers and Industrial Engineering10.1016/j.cie.2015.12.00799:C(300-313)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.cie.2015.12.007

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents