FORMULATIONS FOR THE VEHICLE ROUTING PROBLEM WITH GLOBAL SYNCHRONIZATION AND D-RELAXED PRIORITIES

The Vehicle Routing Problem with Relaxed Priority (VRP-RP) extends the classical Vehicle Routing Problem by incorporating priority levels among customers through the d-relaxed priority rule, which allows limited flexibility in the service order while preserving a priority hierarchy. In this context, the rule can be applied under two frameworks: the Local Timing model, where priority constraints are enforced within each vehicle route independently, and the Global Timing model, where priorities must be respected across all routes simultaneously. This wirk proposes and analyzes four compact vehicle flow-based mathematical formulations for the Global Timing VRP with the d-relaxed priority rule. The approaches include a vehicle-based formulation, a vehicle-type formulation to reduce symmetry, a formulation that separates routing and vehicle assignment decisions, and a formulation based on a total ordering of vertices. The formulations are evaluated under two lexicographic objectives: minimizing total routing cost followed by makespan, and minimizing makespan followed by total cost. Computational experiments compare the formulations and analyze the impact of the relaxation parameter d on solution cost and scheduling performance.