Design and Optimization of Dynamic Routing Problems with Time Dependent Travel Times

Summary The worldwide transportation of cargo is steadily growing and forwarding agencies handling less-than-truckload freight are no exception. The performance of these companies is inuenced strongly by varying transport times between two consecutive points. Surprisingly, traffic information is hardly used within the forwarding industry, even though vehicle location is available in real-time. Numerous unknown customer orders, increasingly received shortly before the actual pickup, are impacting the performance, too. Typical forwarding agencies perform the pickups and the deliveries conjoined. They have to cope with hundreds of pickups and deliveries each day and a few tens of vehicles are necessary to service the customers in the short-distance traffic region. Furthermore, inquiries of business customers cannot be neglected. In the following we focus on one part of the problem dealing with the integration of varying travel times, often resulting in late deliveries and penalties. Especially in urban areas for many roads rush hour traffic jams are known, but this information is hardly used within forwarding agencies. In particular, real-time approaches solving pickup and delivery problems (PDP) with inhomogeneous goods, capacities of general cargo, time windows, varying travel times, and unknown customer orders, which cannot be neglected, are missing. Thus, the objective is to develop a customized dynamic routing model capable of handling all requirements and assisting forwarding agencies in routing vehicles efficiently in real-time.