Optimal solution to the vehicle routing problem by adopting a meta-heuristic algorithm

ABSTRACT

The delivery service provided by large-scale retailers continues to grow as online sales occupy an increasingly large share of the market. This study aims to tease out efficient vehicle scheduling times as well as optimal delivery routes by applying meta-heuristic algorithms. Monthly data on existing routes were obtained from a branch of Korea’s leading large-scale online retailer. The first task was to examine the status of existing routes by comparing delivery routes created using Dijkstra’s algorithm with existing delivery routes and their vehicle scheduling. The second task was to identify optimal delivery routes through a comparative analysis of the genetic algorithm and Tabu search algorithm, known for its superior applicability amongst other meta-heuristic algorithms. These findings demonstrate that the optimal vehicle routing problem not only has the potential to reduce distribution costs for operators and expedite delivery for consumers, but also the added social benefit of reduced carbon emissions.

KEYWORDS:

• Dynamic vehicle routing problem
• meta-heuristic algorithm
• tabu search
• linear optimization
• cost reduction

Additional information

Funding

This work was supported by the Pukyong National University Research Abroad Fund in 2015 [grant number C-D-2015-0358].