A Constraint Programming Model for the Vehicle Routing Problem with Multiple Time Windows

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review


In this paper, we address the vehicle routing problem with multiple time windows (VRPMTW), which extends the classic vehicle routing problem to allow customers to be visited only within one or more time windows. We propose a constraint programming (CP) model for the VRPMTW and apply model-strengthening techniques such as fixing variables and adding interval variables to improve the model’s performance. The model’s effectiveness is demonstrated by comparing its performance against an existing mixed-integer programming model. The study also analyzes the differences in solver performance and evaluates the impact of instance characteristics on the solvability of the problem instances. Our study demonstrates the benefits of using a CP model with model-strengthening techniques for solving medium-sized instances of the VRPMTW.


Original languageEnglish
Title of host publicationComputational Logistics - 14th International Conference, ICCL 2023, Proceedings
EditorsJoachim R. Daduna, Gernot Liedtke, Xiaoning Shi, Stefan Voß
Number of pages15
Publication statusPublished - 2023

External IDs

Scopus 85172396482
dblp conf/iccl/Linss23
Mendeley 8826d446-cfe4-3002-9cde-6068b29edf8b


DFG Classification of Subject Areas according to Review Boards

Subject groups, research areas, subject areas according to Destatis


  • constraint programming, multiple time windows, vehicle routing