Search Word(s) in Title, Keywords, Authors, and Abstract: Kwangcheol Shin

A Geometrical Center based Two-way Search Heuristic Algorithm for Vehicle Routing Problem with Pickups and Deliveries
Kwangcheol Shin
Page: 237~242, Vol. 5, No.4, 2009
10.3745/JIPS.2009.5.4.237
Keywords: Vehicle Routing Problem, Heuristic Algorithm, Initial Solution
Show / Hide 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.