Improvement of CVRP and MTVRP Solution using Local Search Method and its Implementation Using Google Map

DOI

10.2991/icomse-17.2018.21How to use a DOI?

Keywords

local search, CVRP, MTVRP, google map

Abstract

Vehicle Routing Problem (VRP) is an issue for designing the route for distributing goods from one depot to a number of customers, in such way to minimize cost, every customer visited just once, all routes begin and ends at the depot, as well as the total demand of all customers on the route should not violate capacity of vehicles. There are several variants of VRP; two of them are Capacitated Vehicle Routing Problem (CVRP) and Multiple Trip Vehicle Routing Problem (MTVRP). Routes in such variants built by a certain algorithm, such as Sequential Insertion, Clarke-Wright algorithm, or built randomly as well. These must be refined because they are not provided the best result. This article discusses about refining solution of CVRP and MTVRP. The improvement involves local search method. This method initializes neighborhood list containing six inter-route moves: Shift (1,0), Swap (1,1), Shift (2,0), Swap (2,1), Swap(2,2) and Cross operation. At the main iteration, one of the neighborhoods is randomly selected, and the best move is selected as a new solution. If the new solution is better than the initial solution, four intra-route structures are operated, that is Or-opt, 2-opt, Exchange, and Reinsertion. The algorithm is implemented in a web-based application. Google Map is used to give real data about customer position and the route built, as well as its visualization in the map. From the test, the algorithm can improve the initial result built by Sequential Insertion and Clarke-Wright algorithm, in the form of shorter route and number of vehicles used.

Copyright

© 2018, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Sapti Wahyuningsih
AU  - Darmawan Satyananda
PY  - 2017/08
DA  - 2017/08
TI  - Improvement of CVRP and MTVRP Solution using Local Search Method and its Implementation Using Google Map
BT  - Proceedings of the 1st Annual International Conference on Mathematics, Science, and Education (ICoMSE 2017)
PB  - Atlantis Press
SP  - 202
EP  - 206
SN  - 2352-5398
UR  - https://doi.org/10.2991/icomse-17.2018.21
DO  - 10.2991/icomse-17.2018.21
ID  - Wahyuningsih2017/08
ER  -