A deterministic annealing algorithm for road haulage in intermodal freight transport

This paper discusses the pre- and end-haulage by road of containers handled by an inland intermodal barge terminal. Pre- and end-haulage of intermodal barge terminals involves the pickup or delivery of containers by road at customer locations. The drayage of containers in the service area of an intermodal terminal is modelled as a Full Truckload Pickup and Delivery Problem with Time Windows (FTPDPTW). The pickup and delivery problem (PDP) is an extension to the classical Vehicle Routing Problem (VRP) where customers may both receive and send goods. A fleet of vehicles is required to pickup and/or deliver goods at customer locations. 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. In the Full Truckload Pickup and Delivery Problem (FTPDP) a vehicle carries a single load. In the operational planning problem under investigation, a full truckload is assumed to be a single container. Hard time windows are imposed at customer locations. A time window represents the time interval in which the service at a customer must start. When a time window is hard, late services are not allowed. The vehicle must arrive before the latest possible service time at each customer location. Time constraints may also be related to vehicles. In reality vehicles are not available all the time. In this case a time window refers to the time interval in which the vehicle is available. In the pre- and end-haulage of intermodal containers substantial cost and time savings may be realized by merging pickup and delivery customers in a single trip. An insertion heuristic based on merging pickup and delivery customers is used to construct initial solutions. A local search procedure is applied to improve a feasible solution obtained by the insertion heuristic. In this paper a deterministic annealing algorithm is presented as a post-optimization phase for solutions found by the multistart local search procedure. Deterministic annealing (DA), also referred to as 'threshold accepting', is a deterministic variant of simulated annealing (SA). The mechanism of the DA algorithm is demonstrated with a numerical example. A sensitivity analysis is performed to assess the robustness of the DA algorithm to changes in the parameters Tmax and ΔT and with respect to the quality of the initial solution.

Publication year:2009

Accessibility:Closed