casa 20(21): e5

Research Article

Ant Colony-based Tabu List Optimization for Minimizing the Number of Vehicles in Vehicle Routing Problem with Time Window Constraints

Download233 downloads
  • @ARTICLE{10.4108/eai.12-5-2020.166041,
        author={J.L.E.K Fendji and M.V.K. Yakam and M.D. Fendji},
        title={Ant Colony-based Tabu List Optimization for Minimizing the Number of Vehicles in Vehicle Routing Problem with Time Window Constraints},
        journal={EAI Endorsed Transactions on Context-aware Systems and Applications},
        volume={7},
        number={21},
        publisher={EAI},
        journal_a={CASA},
        year={2020},
        month={8},
        keywords={Vehicle Routing Problem with Time Window, Ant Colony-based Tabu List, number of vehicles, CAPEX minimisation},
        doi={10.4108/eai.12-5-2020.166041}
    }
    
  • J.L.E.K Fendji
    M.V.K. Yakam
    M.D. Fendji
    Year: 2020
    Ant Colony-based Tabu List Optimization for Minimizing the Number of Vehicles in Vehicle Routing Problem with Time Window Constraints
    CASA
    EAI
    DOI: 10.4108/eai.12-5-2020.166041
J.L.E.K Fendji1,*, M.V.K. Yakam1, M.D. Fendji2
  • 1: Computer Engineering, University Institute of Technology, The University of Ngaoundere – Cameroon
  • 2: Faculty of Engineering and Technology, University of Buea, Cameroon
*Contact email: lfendji@gmail.com

Abstract

The Vehicle Routing Problem consists in finding a routing plan for vehicles of identical capacity to satisfy the demands of a set of customers. Time window constraints mean that customers can only be served within a pre-defined time window. Researchers have intensively studied this problem because of its wide range of applications in logistics. In this paper, we tackle the problem on an economical point of view with a focus on capital expenditure (CAPEX), where the minimizationof the number of vehicles is more important than the total traveling distance. This customization finds its applications in scenarios with limited CAPEX or seasonal/temporary operations. In these cases, the CAPEX should be minimized as much as possible to reduce the overall cost of the operation, while satisfying time window constraints. We provide an Ant Colony Optimization-based Tabu List (ACOTL). We test the proposed approach on the well-known Solomon’s benchmarks. We compare experiments results to Dynamic Programming on small size instances and later to the best-known results in the literature on large size instances. ACOTL allows to reduce the number of vehicles used sometimes up to three units, compared to the best-known results, especially for instances where customers are geographically in clusters randomly distributed with vehicles of low or medium charges.