TITLE:
Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) with Mobility of Certain Customers
AUTHORS:
Yao Franck Yao, Moustapha Diaby, Bi Kouai Bertin Kaye, Adama Coulibaly
KEYWORDS:
Mobile Customer, Two-Phase Decomposition Heuristic Method for Mobile Customers, Time Window, Branch-and-Cut Algorithm
JOURNAL NAME:
Open Journal of Applied Sciences,
Vol.16 No.3,
March
23,
2026
ABSTRACT: Our study is based on modelling the Vehicle Routing Problem with Time Windows (VRPTW) and mobility of certain customers. The distribution network consists of a depot, a uniform fleet of vehicles and several customers, some of whom have mobility. A mobile customer is a customer that has two alternative positions, both with distinct time windows, distinct requests, and distinct service times between positions. The model chooses exactly one position per mobile customer. A mathematical formulation of this problem with a vehicle index is given in the form of a Linear Mixed Integer Program (LMIP). The mathematical model of this problem is solved using the Branch and Cut (B&C) and also using a two-phase decomposition heuristic method for mobile customers (TPDH-FMC). The tests are performed using data from Solomon’s literature adapted to our problem. The results of these two methods were compared. The tests were carried out on 12 instances. For each instance, we obtained 16 results. We had a total of 192 results. The results obtained through these tests show that out of the 192 results obtained, the heuristic gave a better cost for 10 results (5.20%) compared to the (B&C) algorithm. Furthermore, for 15 results (7.81%), the heuristic and the (B&C) algorithm had the same cost.