A local search heuristic for road haulage in intermodal freight transport

Abstract

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 e±ciently. Pre- and end- haulage of intermodal container terminals involves the pickup or delivery of containers 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). So far this operational planning problem in intermodal transport has received only little atten- tion in scienti¯c literature. A literature study of planning problems in intermodal transport shows only two papers dealing with the operational planning of a drayage operator. Wang and Regan [2] propose a hybrid approach to solve a PDP containing one or more intermodal facilities. Only pickup time windows are considered and the number of vehicles is ¯xed. The authors apply time window discretization in combination with a branch and bound method. The closest 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. A local search heuristic is proposed to improve an initial solution obtained by a two phase con- struction heuristic. Considering the nature of the problem, three neighborhoods of the local search procedure are de¯ned. The CROSS operator re- combines pairs of customers of di®erent routes. A second operator, COMBINE, joins two routes into one. Customers are removed from a route and in- serted into another route by the INSERT operator. The CROSS operator is applied ¯rst to ¯nd bet- ter combinations of pickup and delivery customers. Next, the COMBINE and INSERT operators are used to ¯nd a reduction in the ¯xed vehicle costs. The mechanism of the heuristic is demonstrated by a numerical example. Although there is a variation in variable cost and ¯xed vehicle cost after applying the construction heuristic, the improvement heuris- tic is able to reduce the total cost signi¯cantly and solutions of good quality are obtained. Keywords: Intermodal transport, pickup and de- livery problem, pre- and post-haulage, heuristics