A heuristic for the full truckload pickup and delivery problem with time windows

Abstract

The drayage of containers in the service area of an intermodal terminal can be modelled as a Full Truckload Pickup and Delivery Problem with Time Windows (PDPTW). An intermodal transportation system comprises several means of transportation such as road transport, rail transport, seaborne or inland waterway transport. Road transport constitutes a relatively large share of intermodal transport costs. The attractiveness of intermodal transport can be increased by organizing the road segment in the intermodal transport chain more efficiently. In this study a full truckload is assumed to be a single container. A delivery activity to a consignee starts from the intermodal terminal with a full container and a pickup activity returns a container to the intermodal terminal for shipment by barge. The Pickup and Delivery Problem (PDP) is an extension to the classical Vehicle Routing Problem (VRP) where customers may both receive and send goods. Savelsbergh and Sol [2] give a general description of the PDP. A related article to our research is written by Imai et al. [1]. The authors present a heuristic based on Lagrangian relaxation for the drayage problem of intermodal container terminals, without taking time windows into account. Given the economic context, the following optimization problem can be formulated in terms of a vehicle routing problem with full container load. Assuming a homogeneous container type and size, find the optimal assignment of the own fleet to a set of delivery and pickup customer pairs, in order to minimize the total cost of servicing all customers, which includes a fixed vehicle cost and travel cost that is proportional to the distance travelled. All orders are assumed to be known in advance, so the problem is studied in a static environment. The intermodal terminal is open during a prespecified daily time window. All trucks should return to the terminal before the end of the depot window. Time windows at customer locations are assumed to be hard time windows. An insertion heuristic is developed, which consists of two phases to obtain a near-optimal solution. In a first phase pickups and deliveries are combined into pairs. These pairs of customers are inserted into routes in a second phase. Due to the existence of hard time windows, not every pickup customer and delivery customer can be combined into a feasible route. Inconsistencies in time windows are checked first. This check results in a list of feasible combinations. The waiting time between delivery i and pickup j can be limited to a maximum amount. A feasible pair of customers is discarded from the list if the minimum waiting time is larger than allowed. Second, interesting combinations of customers are selected. In forming pairs of pickups and deliveries, both spatial and temporal aspects are to be taken into account. The savings obtained from serving delivery i and pickup j should be as large as possible. The time window slack between customers i and j should be as small as possible. Weights are given to each objective in order to re- 1 flect its relative importance. This process is repeated until no further feasible combinations exist between the remaining pickup customers and delivery customers. The remaining customers are inserted into individual routes and form an imaginary pair with a dummy customer. An opportunity cost for not choosing the best combination for a delivery i or pickup j can also be taken into account. In a second phase routes are constructed consecutively. The first route is serviced by the vehicle with the lowest fixed cost. Vehicles are used in increasing order of their fixed costs. Pairs of customers are inserted into routes in increasing order of their latest start time. In case insertion into multiple existing routes is possible, the pair of customers is added to the existing route with the smallest waiting time between the previous pair. When no feasible insertions in existing routes are possible, the pair of customers is assigned to an unused vehicle to create a new route. The heuristic procedure is illustrated by means of several examples.