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


Kwangcheol Shin, Journal of Information Processing Systems Vol. 5, No. 4, pp. 237-242, Dec. 2009  

https://doi.org/10.3745/JIPS.2009.5.4.237
Keywords: Vehicle Routing Problem, Heuristic Algorithm, Initial Solution
Fulltext:

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.


Statistics
Show / Hide Statistics

Statistics (Past 3 Years)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.




Cite this article
[APA Style]
Shin, K. (2009). A Geometrical Center based Two-way Search Heuristic Algorithm for Vehicle Routing Problem with Pickups and Deliveries. Journal of Information Processing Systems, 5(4), 237-242. DOI: 10.3745/JIPS.2009.5.4.237.

[IEEE Style]
K. 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. 2009. 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.