The Variable Neighborhood Search for a Consistent Vehicle Routing Problem under the Shift Length Constraints

I. N. Kulachenko, P. A. Kononova, Y. A. Kochetov, A. A. Kurochkin

Research output: Contribution to journalConference articlepeer-review

1 Citation (Scopus)


This paper addresses a new real-world application of vehicle routing planning in a finite time horizon. A company in the small package shipping industry has a limited fleet of identical vehicles in some depots and must serve a set of clients. There is a frequency for each client stating how often this client must be visited. Time intervals between two consecutive visits must be the same but the visiting schedule is flexible. To get some competitive advantage, a company tries to increase the service quality. To this end, each client should be visited by one driver only. The goal is to minimize the total traveling distance for all vehicles over the planning horizon under the frequency constraints and driver shift length constraints. We present an integer linear programming model for this new consistent vehicle routing problem. To find near optimal solutions, we design the Variable Neighborhood Search metaheuristic with nine neighborhood structures. The driver shift length constraints are penalized and included in the objective function. Empirical results for real test instances from Orenburg region in Russia with up to 900 clients and four weeks in the planning horizon are discussed.

Original languageEnglish
Pages (from-to)2314-2319
Number of pages6
JournalIfac papersonline
Issue number13
Publication statusPublished - Sep 2019
Event9th IFAC/IFIP/IFORS/IISE/INFORMS Conference on Manufacturing Modelling, Management and Control (IFAC MIM) - Berlin, Germany
Duration: 28 Aug 201930 Aug 2019


  • Operations research
  • mathematical models
  • optimization problems
  • time scheduling
  • search methods
  • routing algorithms
  • computer experiments
  • Routing algorithms
  • Computer experiments
  • Search methods
  • Mathematical models
  • Optimization problems
  • Time scheduling


Dive into the research topics of 'The Variable Neighborhood Search for a Consistent Vehicle Routing Problem under the Shift Length Constraints'. Together they form a unique fingerprint.

Cite this