Applying an Improved Ant Colony Optimization to solve the Homogeneous Fixed Fleet Close Open Mixed Vehicle Routing Problem

摘要

We consider a vehicle routing problem starting from a depot to serve customers whose demands are deterministic using company vehicles. However, the capacities of their own vehicles cannot fulfill all customer demands. Thus, the company must hire vehicles with several vehicle types, each type being defined by a capacity. All company vehicles must return back to the depot, while hiring vehicles do not have to come back to the depot in order to achieve the objective of the minimum total travel distance. This mentioned characteristic of the problem are called Homogeneous Fixed Fleet Close Open Mixed Vehicle Routing Problem (HFFCOMVRP) which is an NP-Hard problem. Therefore, this research presents applying ant colony optimization which is meta-heuristic algorithms for solving complex optimization problems to find good solutions with acceptance in computation time. The algorithm presented is developed in Python and then tested against 15 standard problems of Augerat et al. (1995). The ant colony optimization with improving the solution using 2-Opt and one-move heuristics is efficient in simultaneously determining the open and close routes in the solutions with a wide range of vehicle capacities. It provides the best solution for 12 out of 15 problems