![[mmi2023 2025-04-27-10.svg]] %%[[mmi2023 2025-04-27-10|🖋 Edit in Excalidraw]]%% [[Flexibility and Coordination in Transportation.txt]] # Comparison of Routing Formulation Approaches Based on Professor Jacquillat's presentation on flexibility and coordination in on-demand transportation, I've created this comparison table of different routing formulation approaches: | Feature | Arc-Based Formulation | Route-Based Formulation | Subpath-Based Formulation | | --------------------------- | --------------------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------- | --------------------------------------------------------------- | | **Description** | Optimizes decisions for connections between individual stops (e.g., "Do I pick up Alice then Bob?") | Optimizes over entire routes (complete sequences from origin to destination) | Optimizes over subpaths (segments between empty vehicle states) | | **Variables** | Individual arcs between stops | Complete vehicle routes | Partial routes that begin and end with empty vehicles | | **Polyhedral Structure** | Very weak | Much tighter | Tight while maintaining manageability | | **Number of Variables** | Fewer variables | Exponential number of variables | Moderate number of variables | | **Scalability** | Poor for large instances | Limited by exponential growth | Good balance of tractability and performance | | **Solution Method** | Direct formulation | Branch and price algorithms | Time-space network optimization | | **Flexibility Integration** | Difficult to incorporate flexibility | Can incorporate flexibility but at high computational cost | Efficiently incorporates vehicle-customer coordination | | **Real-time Applicability** | Not suitable for real-time applications | Computationally intensive for real-time decisions | Capable of solving large instances in seconds | [[🗄️🧠charlie]]