Dynamic vehicle routing with time windows in theory and practice.

Area of Science:

• Operations Research
• Combinatorial Optimization
• Logistics Management

Background:

• The vehicle routing problem (VRP) is a key challenge in logistics.
• Real-world VRPs often involve dynamic changes in orders and strict time windows.
• Existing online optimization algorithms for dynamic VRP typically do not incorporate time windows.

Purpose of the Study:

• To address the dynamic vehicle routing problem with time windows (DVRPTW).
• To develop and evaluate an algorithm capable of on-the-fly schedule generation for delivery services.
• To create and utilize adapted benchmarks reflecting real-world dynamic routing scenarios.

Main Methods:

• A practical problem modeled on a delivery company's daily routing procedure.
• Development of a multiple ant colony algorithm (MACS) integrated with local search.
• Testing on a novel benchmark derived from Solomon's benchmarks with dynamically revealed orders.
• In-situ field study with a surveillance company to assess real-world applicability.

Main Results:

• The proposed MACS algorithm demonstrated superior performance on the academic benchmark problem.
• A high-performing variant of the MACS algorithm was identified.
• The algorithm was successfully integrated and tested in a real-world surveillance company's operations.
• Significant improvements in solution quality were observed compared to the company's existing procedure.

Conclusions:

• The MACS algorithm is effective for solving the dynamic vehicle routing problem with time windows.
• The approach offers practical benefits for real-world logistics and scheduling challenges.
• The study highlights the importance of adapted benchmarks for evaluating dynamic routing algorithms.