Modal-Shift Transportation Problem

Background

Reducing total transportation costs is one of the important problems for logistics companies. Designing a transportation network with minimum cost includes two problems: One is to determine delivery routes of orders and the other is to determine the schedules of carriers. The scheduling problem includes the selection of carriers from possibilities such as trucks, trains, ships, and airplanes (the modal shift problem^*1), which has a great impact on the total cost. In order to solve this problem, a lot of studies have been done on such transportation problems as the Less-Than-Truckload problem, but in many cases these studies did not consider time windows (but considered only the sizes of the loads and the travel times). In practice, it is also necessary to consider time windows, because some modes (such as trains and airplanes) are prescheduled and we should avoid long waiting times.

*1: Modal shift means to consider shifts from trucks to railways or maritime transport, which are more efficient with respect to costs and CO₂ emission. Optimization technology in MSTP can be utilized not only for reducing transportation cost but also for reducing CO₂ emission.

Solution

An MSTP (Modal-Shift Transportation Planner) is a system that solves such problems with time windows. The MSTP finds a feasible schedule for carriers and delivery orders that minimizes total costs for various given sets of facilities, delivery orders, and carriers. Each delivery order is specified by its size, departure facility, destination, EST (earliest start time), and deadline. Each carrier is specified by its capacity, availability, and its departure and arrival times (if prescheduled). The carrier can have multiple legs (e.g., in the figure below, a carrier leaves D for B and returns to D). The latest version of the MSTP considers throughputs of the facilities. Because small facilities cannot handle a lot of delivery orders at one time, it is important in practice to consider the throughputs of facilities.

The MSTP consists of two major algorithms: One algorithm determines delivery routes for delivery orders when the schedules of the carriers are fixed, and the other determines the schedules of the carriers when the delivery routes of the delivery orders are fixed. By using the two algorithms iteratively, the MSTP finds an optimal schedule.

In our simulations with a Japanese logistics company, the MSTP produces a solution with approximately 10 percent cost reduction compared to an actual schedule used by the company.

References

• Hiroyuki Okano, Hiroki Yanagisawa and Kunikazu Yoda, "Less-Than Truckload Network Design Problem with Leadtime," in Proceedings of the 18th RAMP Symposium, Operations Research Society ofJapan, pp. 77--91, 2006. (in Japanese)
• Masami Amano, Takayuki Yoshizumi and Hiroyuki Okano, "Freight simulation: the modal-shift transportation planning problem and its fast steepest descent algorithm," in Proceedings of Winter Simulation Conference 2003, pp. 1720-1728, 2003.