Solving Capacitated Closed Vehicle Routing Problem with Time Windows (CCVRPTW) using BRKGA with local search

7th AIC‐ICMR on Sciences and Engineering 2017

自然科学;工业技术

Prasetyo, H.^1 ; Alfatsani, M.A.^2 ; Fauza, G.^3

Pusat Studi Logistik Dan Optimisasi Industri (PUSLOGIN), Dept. of Industrial Engineering, Universitas Muhammadiyah, Surakarta, Indonesia^1

Dept. of Industrial Engineering, Universitas Muhammadiyah, Surakarta, Indonesia^2

Dept. of Food Technology, Universitas Sebelas Maret, Surakarta, Indonesia^3

关键词: Algorithm design;    Algorithm parameters;    Distribution costs;    Effective algorithms;    Product distributions;    Vehicle capacity;    Vehicle routing problem;    Vehicle routing problem with time windows;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/352/1/012014/pdf
DOI  :  10.1088/1757-899X/352/1/012014

来源: IOP

【 摘 要 】

The main issue in vehicle routing problem (VRP) is finding the shortest route of product distribution from the depot to outlets to minimize total cost of distribution. Capacitated Closed Vehicle Routing Problem with Time Windows (CCVRPTW) is one of the variants of VRP that accommodates vehicle capacity and distribution period. Since the main problem of CCVRPTW is considered a non-polynomial hard (NP-hard) problem, it requires an efficient and effective algorithm to solve the problem. This study was aimed to develop Biased Random Key Genetic Algorithm (BRKGA) that is combined with local search to solve the problem of CCVRPTW. The algorithm design was then coded by MATLAB. Using numerical test, optimum algorithm parameters were set and compared with the heuristic method and Standard BRKGA to solve a case study on soft drink distribution. Results showed that BRKGA combined with local search resulted in lower total distribution cost compared with the heuristic method. Moreover, the developed algorithm was found to be successful in increasing the performance of Standard BRKGA.