A Geometrical Center based Two-way Search Heuristic Algorithm for Vehicle Routing Problem with Pickups and Deliveries

Kwangcheol Shin
Volume: 5, No: 4, Page: 237 ~ 242, Year: 2009
10.3745/JIPS.2009.5.4.237
Keywords: Vehicle Routing Problem, Heuristic Algorithm, Initial Solution
Full Text:

Abstract
The classical vehicle routing problem (VRP) can be extended by including customers who want to send goods to the depot. This type of VRP is called the vehicle routing problem with pickups and deliveries (VRPPD). This study proposes a novel way to solve VRPPD by introducing a two-phase heuristic routing algorithm which consists of a clustering phase and uses the geometrical center of a cluster and route establishment phase by applying a two-way search of each route after applying the TSP algorithm on each route. Experimental results show that the suggested algorithm can generate better initial solutions for more computer-intensive meta-heuristics than other existing methods such as the giant-tour-based partitioning method or the insertion-based method.

Article Statistics
Multiple requests among the same broswer session are counted as one view (or download).
If you mouse over a chart, a box will show the data point's value.


Cite this article
IEEE Style
Kwangcheol Shin, "A Geometrical Center based Two-way Search Heuristic Algorithm for Vehicle Routing Problem with Pickups and Deliveries," Journal of Information Processing Systems, vol. 5, no. 4, pp. 237~242, 2009. DOI: 10.3745/JIPS.2009.5.4.237.

ACM Style
Kwangcheol Shin, "A Geometrical Center based Two-way Search Heuristic Algorithm for Vehicle Routing Problem with Pickups and Deliveries," Journal of Information Processing Systems, 5, 4, (2009), 237~242. DOI: 10.3745/JIPS.2009.5.4.237.