An efficient mathematical model and step-by-step solution method for the capacitated vehicle routing problem via customer marking

چکیده مقاله

This study investigates the delivery vehicle routing problem (VRP) in urban areas, where the demands of geographically dispersed customers must be fulfilled by a heterogeneous fleet of capacity-constrained vehicles while minimizing total travel distance. VRP is a well-known and highly complex combinatorial optimization problem, for which diverse solution methods have been proposed. In conventional routing formulations, binary variables are typically defined for every customer pair to determine traversals, causing model dimensions to grow quadratically with the number of customers. To overcome this limitation, this paper introduces a novel mathematical formulation that drastically reduces the number of binary variables by sequencing visited customers along selected routes. Furthermore, to efficiently handle large-scale instances, an iterative, step-by-step solution method based on sequential customer marking is developed. Extensive implementations on various instances demonstrate the high computational efficiency and practical applicability of the proposed approach.