This paper investigates local search approach for solving the min-max capacitated vehicle routing problem with different neighborhood structures. We also propose a combined function instead of the objective function itself for controlling the local search. Experimental results on different datasets show the efficiency of our proposed algorithms compared to previous techniques. | Journal of Computer Science and Cybernetics, , (2017), 3–18 DOI SOLVING MIN-MAX CAPACITATED VEHICLE ROUTING PROBLEM BY LOCAL SEARCH NGUYEN VAN SON1,2 , PHAM QUANG DUNG1 , BUI QUOC TRUNG3 , NGUYEN THANH HOANG1 1 Ha Noi University of Science and Technology of Cryptography Techniques 3 Viettel Research and Development Institute 1,2 sonnv188@; dungpq@ 2 Academy Abstract. Vehicle routing is a class of combinatorial optimization problems in transportation and logistics. Min-max capacitated vehicle routing is a problem of this class in which the length of the longest route must be minimized. This paper investigates local search approach for solving the min-max capacitated vehicle routing problem with different neighborhood structures. We also propose a combined function instead of the objective function itself for controlling the local search. Experimental results on different datasets show the efficiency of our proposed algorithms compared to previous techniques. Keywords. Vehicle routing, local search, min-max vehicle routing, combinatorial optimization. 1. INTRODUCTION A large number of applications involve sets of clients that must be served by vehicles located at a common depot. Problems which optimize the selection of routes for the vehicles, are referred to as vehicle routing problem [27, 19]. Solving these problems is very hard and is still an active research topic which attracts the attention of many computer scientists due to their impact to the society and the economy. Many variants of vehicle routing applications have been studied in the literature, for example, Capacitated Vehicle Routing problem (CVRP) [32], Min-Max Vehicle Routing Problem (MMVRP) [1], Vehicle Routing Problem with Time Windows (VRPTW) [9], etc. We consider in this paper the Min-Max Capacitated Vehicle Routing Problem (MMCVRP). The goal of this problem is to ensure that all clients are served as soon as possible such .
