TY - JOUR

T1 - A Hybrid Local Search Algorithm for the Consistent Periodic Vehicle Routing Problem

AU - Kulachenko, I. N.

AU - Kononova, P. A.

PY - 2020/5/1

Y1 - 2020/5/1

N2 - Under consideration is some new real-world application of vehicle routing planning ina finite time horizon. Let a company have a set of capacitated vehicles in some depots and servesome set of customers. There is a frequency for each customer which describes how often thecustomer should be visited. Time intervals between two consecutive visits are fixed, but thevisiting schedule is flexible. To obtain some competitive advantage, the company tries to increasethe service quality. To this end, each customer should be visited by one driver only. The goal is tominimize the total length of the vehicle paths over the planning horizon under the frequencyconstraints and driver shift length constraints. We present a mixed-integer linear programmingmodel for this new consistent capacitated vehicle routing problem. To find near optimal solutions,we design the variable neighborhood search metaheuristic with several neighborhood structures.The driver shift length and capacitated constraints are penalized and included into the objectivefunction. Some numerical results for the real test instances are discussed.

AB - Under consideration is some new real-world application of vehicle routing planning ina finite time horizon. Let a company have a set of capacitated vehicles in some depots and servesome set of customers. There is a frequency for each customer which describes how often thecustomer should be visited. Time intervals between two consecutive visits are fixed, but thevisiting schedule is flexible. To obtain some competitive advantage, the company tries to increasethe service quality. To this end, each customer should be visited by one driver only. The goal is tominimize the total length of the vehicle paths over the planning horizon under the frequencyconstraints and driver shift length constraints. We present a mixed-integer linear programmingmodel for this new consistent capacitated vehicle routing problem. To find near optimal solutions,we design the variable neighborhood search metaheuristic with several neighborhood structures.The driver shift length and capacitated constraints are penalized and included into the objectivefunction. Some numerical results for the real test instances are discussed.

KW - Kernighan–Lin neighborhood

KW - metaheuristic

KW - penalty method

KW - vehicle of limited capacity

UR - http://www.scopus.com/inward/record.url?scp=85087779718&partnerID=8YFLogxK

U2 - 10.1134/S199047892002012X

DO - 10.1134/S199047892002012X

M3 - Article

AN - SCOPUS:85087779718

VL - 14

SP - 340

EP - 352

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 2

ER -