A study in Tabu Search Algorithm to Solve a Special Vehicle Routing Problem

Full Text (PDF, 204KB), PP.48-53

Views: 0 Downloads: 0

Author(s)

Xingrong Yan 1,* Hongan Dong 1

1. Binzhou Polytechnic College, Shandong, China

* Corresponding author.

DOI: https://doi.org/10.5815/ijem.2012.01.08

Received: 2 Nov. 2011 / Revised: 14 Dec. 2011 / Accepted: 24 Jan. 2012 / Published: 29 Feb. 2012

Index Terms

Vehicle Routing Problem, Tabu Search, Meta Heuristic Algorithm

Abstract

In this paper, a kind of special vehicle routing problem based on reality-- vehicle routing problem with facultative demands is presented. The attributes of the problem and the optimization target are described. The mathematical model of the problem is set up. To solve the problem, A meta-heuristic approach called tobu search (TS) is put forward. The neighborhood structure and the parameters of TS algorithm are designed respectively. The proposed algorithm is successfully applied to a case and the result indicates the TS algorithm is practicable and valid.

Cite This Paper

Xingrong Yan,Hongan Dong,"A study in Tabu Search Algorithm to Solve a Special Vehicle Routing Problem", IJEM, vol.2, no.1, pp.48-53, 2012. DOI: 10.5815/ijem.2012.01.08 

Reference

[1] Dantzig G, Ramser J. The truck dispatching problem [J].Management Science,1959

[2] Garey M R,Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco:W h Freeman and Company,1999

[3] Mi,H. The multiple vehicle routing problem with simultaneous delivery and pickup points[J]. Transportation Research A, 1999, 23A: 377_386.

[4] Jan Dethloff. Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up[J]. OR Spektrum, 2008, 23(1): 79_96.

[5] Dethloff,J. “Relation between vehicle routing problems” an insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls[J]. Journal of the Operational Research Society, 2008, 53(1): 15_118.

[6] Salhi,S. and Nagy,G. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling[J]. Journal of the Operational Research Society, 1999, 50(10): 1034_1042.

[7] Mosheiov,G. The traveling salesman problem with pick-up and delivery[J]. European Journal of Operational Research, 2009, 79(2): 299_310.

[8] Kontoravdis,G. and Bard, J. A GRASP for the vehicle routing problem with time windows[J]. ORSA Journal on Computing, 1995, 7(1): 10_23.

[9] Sin C.Ho&Dag Haugland.A Tabu Search for the Vehicle Routing Problem with Time Windows and Split Deliveries,2002.9