Solving the Dynamic Capacitated Vechicle Routing Problem with time Windows: Exact and Hybrid Meta-Heuristic Methods

Hoang Thi Bich Ngoc

Abstract

Transportation companies are crucial part of the logistic chain and they continuously face multiple challenges. One of the key challenges is in delivery, where transport companies must assign available and limited resources to serve various customer in each network while concurrently optimize flow of goods, minimize cost and accede to customer dynamic requests. Therefore, it is necessary to explore and investigate the possibilities towards a routing solution so that the company can stay competitive in the market as well as remain cost-efficient. The goal of this project is to study and develop analytical models and algorithms for effective decision making in resource allocation for a transportation company based on both static and dynamic customer demands. The models and algorithms developed will be applied to case scenarios from transportation company to demonstrate its effectiveness in addressing resource allocation issues. Static and dynamic vehicle routing problem are presented and solved with various optimization approaches.

In static vehicle routing problem, a pure Mixed Integer Programming (MIP) model is introduced to draw towards a global optimal solution. The model not only considers the usual supply-demand constraints but also look at various tight constraints such as vehicle capacity and time windows required by different customers to have overall optimal solution with minimal travelling time. Besides, a hybrid meta-heuristic model with the use of Ant Colony Optimization (ACO) algorithm and other algorithms such as local search, nearest neighborhood (NNH) is built to tackle some inherent issues that Mixed Integer Programming carries.

Dynamic vehicle routing problem which is basically a variant of vehicle routing problem with changes in committed demand and service requirement from customers also studied with various approaches in this paper. With MIP and hybrid meta-heuristic model applied to allow re-planning effectively upon changes, the dynamic problem is a very good platform to test model’s applicability with different scenarios.

The results between different optimization approach demonstrates the effectiveness of hybrid meta-heuristic model in solving vehicle routing problem. It is reactively outstanding in term of run time and providing reliable solution at the same time. Meta-heuristic method is a promising and realistic approach that also can be integrated into real -life application effectively