A Geometrical Center based Two-way Search Heuristic Algorithm for Vehicle Routing Problem with Pickups and Deliveries
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
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.
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.
참고문헌 (24)
- Dantzig GB, "The truck dispatching problem", Manage Sci, 6, pp.80~91 (1959)
- Toth P, "An exact algorithm for the vehicle routing problem with backhauls", Transport Sci, 31, pp.372~385 (1997)
- Mingozzi A, "An exact method for the vehicle routing problem with backhauls", Transport Sci, 33, pp.315~329 (1999)
- Deif I, "Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling", Proceedings of the Babson conference on software uses in transportation and logistic management, pp.75~96 (1984)
- Goetschalckx M, "The vehicle routing problem with backhauls", Eur J Oper Res, 42, pp.39~51 (1989)
- Thangiah SR, "Heuristic approaches to vehicle routing with backhauls and time windows", Comput Oper Res, 23, pp.1043~1057 (1996)
- Duhamel C, "A tabu search heuristic for the vehicle routing problem with backhauls and time windows", Transport Sci, 31, pp.49~59 (1997)
- Toth P, "A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls", Eur J Oper Res, 113, pp.528~543 (1999)
- Brandão J, "A new tabu search algorithm for the vehicle routing problem with backhauls", Eur J Oper Res, 173, pp.540~555 (2006)
- Min H, "The multiple the vehicle routing problem with simultaneous delivery and pick-up points", Transport Res Part A, 5, pp.377~386 (1989)
- Dethloff J, "Vehicle routing and reverse logistics:the vehicle routing problem with simultaneous delivery and pick-up", Oper Res Spektrum, 23, pp.79~96 (2001)
- Dethloff J, "Relation between vehicle routing problems:An insertion heuristic for the vehicle routing problem with simultaneous delivery and pickup applied to the vehicle routing problem with backhauls", J Oper Res Soc, 53, pp.115~118 (2002)
- Angelelli E, "The vehicle routing problem with time windows and simultaneous pick-up and delivery. In: Quantitative Approaches to Distribution Logistics and Supply Chain Management", pp.249~267 (2002), Springer-Verlag
- Tang FA, "Vehicle routing problems with simultaneous pick-up and delivery service", Opsearch, 39, pp.19~33 (2002)
- Tang FA, "A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service", Comp Opns Res, 33, pp.595~619 (2006)
- Nagy G, "The many-to-many location-routing problem", TOP, 6, pp.261~275 (1998)
- Nagy G, "Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries", Eur J Opl Res, 162, pp.126~141 (2005)
- Chen JF, "Vehicle routing problem with simultaneous deliveries and pickups", J Opl Res Soc, 57, pp.579~587 (2006)
- Lin S, "An effective heuristic algorithm for the traveling salesman problem", Opns Res, 21, pp.498~516 (1973)
- "Approche polyèdrale du problème de tournées de véhicules" (1995)[URL]
- Salhi S, "Adaptation of some vehicle fleet mix heuristics", Omega, 20, pp.653~660 (1992)
- Mosheiov G, "The travelling salesman problem with pick-up and delivery", Eur J Oper Res, 79, pp.299~310 (1994)
- Clarke G, "Scheduling of vehicles from a central depot to a number of delivery points", Opns Res, 12, pp.568~581 (1964)
- Nagy G, "A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling", J Opl Res Soc, 50, pp.1034~1042 (1999)