A Metaheuristic for the Pickup and Delivery Problem with Split-Loads and its Extension

• Main Author: YAO, Dai
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2009
• Subjects: loading size problems; metaheuristics for logistics; split loads; tabu search; transportation network; Operations and Supply Chain Management
• Online Access: https://ink.library.smu.edu.sg/etd_coll/1; https://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=1000&context=etd_coll
• Institution: Singapore Management University

In this dissertation, we study improvements in the Pickup and Delivery Problem that can be achieved by allowing multiple vehicle trips to serve a common load. We explore how costs can be reduced through the elimination of the constraint that a load must be served by only one vehicle trip. Specifically, we investigate the problem of routing vehicles to serve loads that have distinct origins and destinations, with no constraint on the amount of a load that a vehicle may serve at a time. We develop a metaheuristic to solve large scale practical size problems in this form and apply the metaheuristic to randomly generated data sets. The metaheuristic is based on a predetermined fixed number of restarts of annealing-like procedure with tabu-lists to avoid cycling in the search process and the annealinglike procedure is to guide the local search in three neighborhoods defined to solve the problem. We test the algorithm on several sets of problem instances generated with different transportation requests and over different load size ranges. The experimental results on these problem sets have shown that benefits are common if split loads are adopted in designing practical sized transportation network for different load size configurations, and the most benefit is achieved when all the loads are just a little above half of the vehicle capacity and have small variations,and this most benefit is around 33% for all the three 75-, 100-, and 125-request problem sets, which overtakes the one reported in previous literature. In a more general setting when some load sizes are greater than the vehicle capacity and have to be split, there are also certain cost reduction if split loads are applied. We also generate numeral tests on different load size ranges and split the loads that are greater than the vehicle capacity using different "splitting" strategy, in term of how much amount to split from the original load to form a new load, and find that there seem to be no optimal "splitting" strategy, which can assure the best quality of solutions using the metaheuristic developed in the dissertation.