A fast and effective insertion algorithm for multi-depot vehicle routing problem with fixed distribution of vehicles and a new simulated annealing approach

Andrew Lim; Wenbin Zhu

doi:10.1007/11779568_32

A fast and effective insertion algorithm for multi-depot vehicle routing problem with fixed distribution of vehicles and a new simulated annealing approach

Andrew Lim
, Wenbin Zhu

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

17 Citations (Scopus)

Abstract

Multi-depot Vehicle Routing Problem has great practical value to the logistics and supply chain management. The fixed distribution of vehicles variant (MDVRPFD) brings it one step closer to the practical use. Based on the simple fact that all sub-routes of an optimal route must be optimal, a new randomized best insertion (RBI) algorithm Is proposed. The proposed insertion algorithm is highly effective in minimizing number of vehicles and fast. Compared to the best known result published for MDVRPFD variant, the solutions generated by this new insertion algorihtm require 20% fewer vehicles. Adopting a generalized n-op neighborhood operator, a Simulated Annealing approach yields a reduction of 12% in total distance compared to best known results of MDVRPFD. © Springer-Verlag Berlin Heidelberg 2006.

Original language	English
Title of host publication	Advances in Applied Artificial Intelligence
Subtitle of host publication	19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2006, Proceedings
Editors	Moonis Ali, Richard Dapoigny
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	282-291
ISBN (Electronic)	978-3-540-35454-3
ISBN (Print)	9783540354536
DOIs	https://doi.org/10.1007/11779568_32
Publication status	Published - 2006
Externally published	Yes
Event	19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (IEA/AIE 2006) - Annecy, France Duration: 27 Jun 2006 → 30 Jun 2006

Publication series

Name	Lecture Notes in Computer Science
Volume	4031
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (IEA/AIE 2006)
Place	France
City	Annecy
Period	27/06/06 → 30/06/06

Research Keywords

Insertion algorithm
MDVRP
MDVRPFD
Meta-heuristic
Sub-route optimization

Access Output

10.1007/11779568_32

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Lim, A., & Zhu, W. (2006). A fast and effective insertion algorithm for multi-depot vehicle routing problem with fixed distribution of vehicles and a new simulated annealing approach. In M. Ali, & R. Dapoigny (Eds.), Advances in Applied Artificial Intelligence: 19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2006, Proceedings (pp. 282-291). (Lecture Notes in Computer Science; Vol. 4031). Springer . https://doi.org/10.1007/11779568_32

Lim, Andrew ; Zhu, Wenbin. / A fast and effective insertion algorithm for multi-depot vehicle routing problem with fixed distribution of vehicles and a new simulated annealing approach. Advances in Applied Artificial Intelligence: 19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2006, Proceedings. editor / Moonis Ali ; Richard Dapoigny. Berlin, Heidelberg : Springer , 2006. pp. 282-291 (Lecture Notes in Computer Science).

@inproceedings{72ab761dbcff477f807e80ad4c614d96,

title = "A fast and effective insertion algorithm for multi-depot vehicle routing problem with fixed distribution of vehicles and a new simulated annealing approach",

abstract = "Multi-depot Vehicle Routing Problem has great practical value to the logistics and supply chain management. The fixed distribution of vehicles variant (MDVRPFD) brings it one step closer to the practical use. Based on the simple fact that all sub-routes of an optimal route must be optimal, a new randomized best insertion (RBI) algorithm Is proposed. The proposed insertion algorithm is highly effective in minimizing number of vehicles and fast. Compared to the best known result published for MDVRPFD variant, the solutions generated by this new insertion algorihtm require 20\% fewer vehicles. Adopting a generalized n-op neighborhood operator, a Simulated Annealing approach yields a reduction of 12\% in total distance compared to best known results of MDVRPFD. {\textcopyright} Springer-Verlag Berlin Heidelberg 2006.",

keywords = "Insertion algorithm, MDVRP, MDVRPFD, Meta-heuristic, Sub-route optimization",

author = "Andrew Lim and Wenbin Zhu",

year = "2006",

doi = "10.1007/11779568\_32",

language = "English",

isbn = "9783540354536",

series = "Lecture Notes in Computer Science",

publisher = "Springer ",

pages = "282--291",

editor = "Ali, \{Moonis \} and Dapoigny, \{Richard \}",

booktitle = "Advances in Applied Artificial Intelligence",

note = "19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (IEA/AIE 2006) ; Conference date: 27-06-2006 Through 30-06-2006",

}

Lim, A & Zhu, W 2006, A fast and effective insertion algorithm for multi-depot vehicle routing problem with fixed distribution of vehicles and a new simulated annealing approach. in M Ali & R Dapoigny (eds), Advances in Applied Artificial Intelligence: 19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2006, Proceedings. Lecture Notes in Computer Science, vol. 4031, Springer , Berlin, Heidelberg, pp. 282-291, 19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (IEA/AIE 2006), Annecy, France, 27/06/06. https://doi.org/10.1007/11779568_32

A fast and effective insertion algorithm for multi-depot vehicle routing problem with fixed distribution of vehicles and a new simulated annealing approach. / Lim, Andrew; Zhu, Wenbin.
Advances in Applied Artificial Intelligence: 19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2006, Proceedings. ed. / Moonis Ali; Richard Dapoigny. Berlin, Heidelberg: Springer , 2006. p. 282-291 (Lecture Notes in Computer Science; Vol. 4031).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - A fast and effective insertion algorithm for multi-depot vehicle routing problem with fixed distribution of vehicles and a new simulated annealing approach

AU - Lim, Andrew

AU - Zhu, Wenbin

PY - 2006

Y1 - 2006

N2 - Multi-depot Vehicle Routing Problem has great practical value to the logistics and supply chain management. The fixed distribution of vehicles variant (MDVRPFD) brings it one step closer to the practical use. Based on the simple fact that all sub-routes of an optimal route must be optimal, a new randomized best insertion (RBI) algorithm Is proposed. The proposed insertion algorithm is highly effective in minimizing number of vehicles and fast. Compared to the best known result published for MDVRPFD variant, the solutions generated by this new insertion algorihtm require 20% fewer vehicles. Adopting a generalized n-op neighborhood operator, a Simulated Annealing approach yields a reduction of 12% in total distance compared to best known results of MDVRPFD. © Springer-Verlag Berlin Heidelberg 2006.

AB - Multi-depot Vehicle Routing Problem has great practical value to the logistics and supply chain management. The fixed distribution of vehicles variant (MDVRPFD) brings it one step closer to the practical use. Based on the simple fact that all sub-routes of an optimal route must be optimal, a new randomized best insertion (RBI) algorithm Is proposed. The proposed insertion algorithm is highly effective in minimizing number of vehicles and fast. Compared to the best known result published for MDVRPFD variant, the solutions generated by this new insertion algorihtm require 20% fewer vehicles. Adopting a generalized n-op neighborhood operator, a Simulated Annealing approach yields a reduction of 12% in total distance compared to best known results of MDVRPFD. © Springer-Verlag Berlin Heidelberg 2006.

KW - Insertion algorithm

KW - MDVRP

KW - MDVRPFD

KW - Meta-heuristic

KW - Sub-route optimization

UR - https://www.scopus.com/pages/publications/33746215718

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-33746215718&origin=recordpage

U2 - 10.1007/11779568_32

DO - 10.1007/11779568_32

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783540354536

T3 - Lecture Notes in Computer Science

SP - 282

EP - 291

BT - Advances in Applied Artificial Intelligence

A2 - Ali, Moonis

A2 - Dapoigny, Richard

PB - Springer

CY - Berlin, Heidelberg

T2 - 19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (IEA/AIE 2006)

Y2 - 27 June 2006 through 30 June 2006

ER -

Lim A, Zhu W. A fast and effective insertion algorithm for multi-depot vehicle routing problem with fixed distribution of vehicles and a new simulated annealing approach. In Ali M, Dapoigny R, editors, Advances in Applied Artificial Intelligence: 19th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2006, Proceedings. Berlin, Heidelberg: Springer . 2006. p. 282-291. (Lecture Notes in Computer Science). Epub 2006 Jun 24. doi: 10.1007/11779568_32

A fast and effective insertion algorithm for multi-depot vehicle routing problem with fixed distribution of vehicles and a new simulated annealing approach

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this