MA4 - Tournées de véhicule / Vehicle Routing 1

This study develops an integrated control and routing framework for systems with behavior responsive demand. The planner determines spatiotemporal intervention policies implemented through routing decisions, where visit frequency and timing influence user behavior through an equilibrium response. The problem is formulated as a Multi Visit Team Orienteering Problem in which inspection schedules act as control variables that shape compliance dynamics across the network.

The framework is particularly suited to patrol based operational settings in which a limited set of mobile agents must be allocated across space and time to influence system outcomes. In such applications, the effectiveness of interventions depends not only on where resources are deployed, but also on how frequently and when locations are revisited. We study this setting in the context of urban parking enforcement, where inspection intensity affects driver compliance and revenue generation. The model incorporates a behavioral equilibrium that links enforcement intensity to user response and captures the feedback between interventions and system state. A recovery time mechanism is introduced to regulate diminishing returns from repeated interventions by enforcing a minimum interval between successive visits.

To solve the resulting high dimensional problem, we develop an adaptive Variable Neighborhood Descent metaheuristic guided by a knapsack based relaxation that estimates effective intervention levels across locations. Computational results show that performance depends critically on the temporal coordination of interventions rather than only their aggregate level. While demonstrated in the context of urban parking enforcement, the framework applies more broadly to patrol based systems in which outcomes depend on the timing and distribution of control actions.

This project develops exact and heuristic methods for the full truckload pickup and delivery vehicle routing problem (FTL-PDVRP). It proposes two compact formulations that eliminate unnecessary vehicle movements to reduce model size and improve efficiency. Heuristic algorithms generate feasible routes, and a route-based set partitioning model selects high-quality solutions for performance comparison.
Keywords:
Full truckload pickup and delivery, compact formulation, heuristic algorithms, set partitioning

We develop and compare several cost-sharing models for cooperative vehicle routing. We examine the issues of fairness and stability in cooperative routing, and show that coalitions served by single routes are sufficient to impose stability conditions. Computational experiments are conducted on randomly generated instances and on a Quebec-based case study.

Uncertain driver availability can severely disrupt supply chain operations. We study this in the context of the production routing problem (PRP) and propose the stochastic PRP with uncertain vehicle availability (SPRP-V). We derive a novel deterministic reformulation, HetPRP, that embeds expected recourse costs into first-stage routing decisions, eliminating the need for stochastic decomposition. Computational results show that HetPRP significantly outperforms both the extensive form formulation and a tailored Benders decomposition that exploits the integrality of second-stage subproblems.