Advanced Heuristics in Transportation and Logistics

Advanced Heuristics in Transportation and Logistics

Christos D. Tarantilis

Michel Gendreau

Diomidis Spinellis

You are required to plan the routes of your company’s 250 delivery trucks from your company’s 12 depots to the city’s 5000 vendor locations. Traffic patterns, accidents and breakdowns, vendor-specified delivery time windows, perishable goods, returned empty packages, and product shortages at specific depots further complicate the picture. And, by the way, yesterday’s plan is no longer applicable, because heavy snowfall overnight has invalidated your estimations of the trucks’ speeds; you need a new plan by daybreak, in two hours. Where do you start?

In today’s global transportation and logistics environment, industries require computational and simulation-based methods that will lead to faster transactions, reduced operating costs, and improved performance and customer service. They also want methods and tools that provide more control and flexibility in their operations such as production and location planning, warehousing, distribution, and transportation.

Transportation and logistics organizations often face large-scale combinatorial problems on both operational and strategic levels. In such problems, all possible combinations of decisions and variables must be examined to find a solution; consequently, no partial enumeration-based exact algorithm can consistently solve them. This occurs because sharp lower bounds on the objective value are hard to derive, thus causing a slow convergence rate [1]. By exploiting problem-specific characteristics, classical heuristic methods, such as constructive and iterative local search methods, aim at a relatively limited exploration of the search space, thereby producing acceptable-quality solutions in modest computing times.

As a major departure from a classical heuristic, a metaheuristic method implies a higher-level strategy controlling a lower-level heuristic method. Metaheuristics...