Solving the Pick up and Delivery Problem with Time Windows Using "Squeaky Wheel" Optimization with Local Search
Abstract
The Pickup and Delivery Problem with Time Windows (PDPTW) is an important problem in fleet planning where decisions can involve not only dispatching company fleets but also the selection of carriers on certain routes. In this problem, vehicles travel to a variety of locations to deliver or pick up goods and to provide services. The increasing costs for additional vehicles motivate managers to optimize fleet usage. Managers also seek to achieve economical use of fuel, maintenance and overtime costs by minimizing travel distance and duration. As such, PDPTW impacts the interface of supplier-customer relationship management in the supply chain process and is essential for any linked decision support system. In this paper, we describe deployment of a relatively new optimization technique, known as "Squeaky Wheel" Optimization (SWO), to the PDPTW. Our objective is to minimize the fleet size, travel distances, schedule durations and waiting times. We implement an SWO framework for the PDPTW, integrating Solomonís Insertion Heuristic and Local Search into a construction phase. In addition, we design a blame assignment and prioritizing schemes to facilitate problem solution. Our new method has been tested on the Solomonís 56 benchmark cases for which we have obtained encouraging results with this new technique.