A reoptimization algorithm for the shortest path problem with time windows
From MaRDI portal
Publication:1123818
DOI10.1016/0377-2217(88)90034-3zbMath0677.90080OpenAlexW2091020754MaRDI QIDQ1123818
Martin Desrochers, François Soumis
Publication date: 1988
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0377-2217(88)90034-3
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10) Dynamic programming (90C39)
Related Items
The flexible and real-time commute trip sharing problems ⋮ Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context ⋮ A column generation approach for a multi-attribute vehicle routing problem ⋮ Tramp ship routing and scheduling with voyage separation requirements ⋮ The discrete time window assignment vehicle routing problem ⋮ An assignment-based lower bound for a class of two-machine flow shop problems ⋮ Using the primal-dual interior point algorithm within the branch-price-and-cut method ⋮ Implementation of a three-stage approach for the dynamic resource-constrained shortest-path sub-problem in branch-and-price ⋮ A profit-maximization location-routing-pricing problem: a branch-and-price algorithm ⋮ A column generation approach to the heterogeneous fleet vehicle routing problem ⋮ Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework ⋮ Exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows ⋮ The cross-entropy method for solving bi-criteria network flow problems in discrete-time dynamic networks ⋮ Efficient frameworks for greedy split and new depth first search split procedures for routing problems ⋮ Dynamic constraint and variable aggregation in column generation ⋮ Solving Stochastic Ship Fleet Routing Problems with Inventory Management Using Branch and Price ⋮ The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm ⋮ Minimum time paths in a network with mixed time constraints. ⋮ A computational study of solution approaches for the resource constrained elementary shortest path problem ⋮ Shipping problems with body clock constraints. ⋮ Updating network flows given multiple, heterogeneous arc attribute changes ⋮ The pickup and delivery problem with time windows ⋮ Computational complexity of convoy movement planning problems ⋮ A column generation approach for the split delivery vehicle routing problem ⋮ A model to optimize placement operations on dual-head placement machines ⋮ A dynamic programming solution of a shortest path problem with time constraints on movement and parking ⋮ Formulations and exact algorithms for the vehicle routing problem with time windows ⋮ A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation ⋮ Exact approaches for integrated aircraft fleeting and routing at TunisAir ⋮ Dynamic programming approaches to solve the shortest path problem with forbidden paths ⋮ Nodal aggregation of resource constraints in a shortest path problem ⋮ Unnamed Item ⋮ A solution approach to find the critical path in a time-constrained activity network ⋮ Lagrangian duality applied to the vehicle routing problem with time windows ⋮ Performances improvement of the column generation algorithm: application to vehicle routing problems ⋮ Vehicle routing with soft time windows and stochastic travel times: a column generation and branch-and-price solution approach ⋮ A survey of resource constrained shortest path problems: Exact solution approaches ⋮ Fleet assignment and routing with schedule synchronization constraints ⋮ Analyse de sensibilité pour les problèmes linéaires en variables 0-1 ⋮ Locomotive assignment with heterogeneous consists at CN North America ⋮ Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function ⋮ The split heterogeneous vehicle routing problem with three-dimensional loading constraints on a large scale ⋮ Shortest path with acceleration constraints: complexity and approximation algorithms ⋮ The orienteering problem with time windows applied to robotic melon harvesting ⋮ Minimization of travel time and weighted number of stops in a traffic-light network ⋮ Branch-and-price for staff rostering: an efficient implementation using generic programming and nested column generation ⋮ An adapted step size algorithm for a 0-1 biknapsack Lagrangean dual
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Netzwerk-Veränderungen und Korrektur kürzester Weglängen von einer Wurzelmenge zu allen anderen Knoten
- Plus court chemin avec contraintes d'horaires
- Reoptimization procedures in shortest path problem
- Routing with time windows by column generation
- A note on the problem of updating shortest paths
- On Finding and Updating Spanning Trees and Shortest Paths
- Etude Et Extension D’Un Algorithme De Murghland
- Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
- A new shortest path updating algorithm
