New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows

Diego Pecin
Diego Pecin
[email protected]
Département de mathématiques et de génie industriel, Polytechnique Montréal, Montréal QC H3T 1J4, Canada; and Group for Research in Decision Analysis (GERAD), HEC Montréal 3000, QC H3T 2A7, Canada
Search for more papers by this author
,
Claudio Contardo
Corresponding Author
Claudio Contardo
[email protected]
Group for Research in Decision Analysis (GERAD), HEC Montréal 3000, QC H3T 2A7, Canada; and Département de management et technologie, ESG UQÀM, Montréal, QC H2X 3X2, Canada
Search for more papers by this author
,
Guy Desaulniers
Guy Desaulniers
[email protected]
Département de mathématiques et de génie industriel, Polytechnique Montréal, Montréal QC H3T 1J4, Canada; and Group for Research in Decision Analysis (GERAD), HEC Montréal 3000, QC H3T 2A7, Canada
Search for more papers by this author
,
Eduardo Uchoa
Eduardo Uchoa
[email protected]
Departamento de engenharia de produção, Universidade Federal Fluminense, Niterói, RJ, 24220-900, Brazil
Search for more papers by this author

Département de mathématiques et de génie industriel, Polytechnique Montréal, Montréal QC H3T 1J4, Canada; and Group for Research in Decision Analysis (GERAD), HEC Montréal 3000, QC H3T 2A7, Canada

Search for more papers by this author

Claudio Contardo

Corresponding Author

Claudio Contardo

[email protected]

Group for Research in Decision Analysis (GERAD), HEC Montréal 3000, QC H3T 2A7, Canada; and Département de management et technologie, ESG UQÀM, Montréal, QC H2X 3X2, Canada

Search for more papers by this author

Guy Desaulniers

[email protected]

Search for more papers by this author

Eduardo Uchoa

[email protected]

Departamento de engenharia de produção, Universidade Federal Fluminense, Niterói, RJ, 24220-900, Brazil

Search for more papers by this author

Published Online:26 Jun 2017https://doi.org/10.1287/ijoc.2016.0744

Supplemental Material

ijoc.2016.0744.sm1.pdf

Cited by
- A branch-and-price-and-cut algorithm for divisional seru formation and scheduling problem considering section construction
  European Journal of Operational Research, Vol. 332, No. 3
- Improving last-mile delivery efficiency using cargo bikes and autonomous robots
  European Journal of Operational Research, Vol. 333, No. 1
- Contextual Stochastic Vehicle Routing with Time Windows
  Breno Serrano,
  Alexandre M. Florio,
  Stefan Minner,
  Maximilian Schiffer,
  Thibaut Vidal
  22 June 2026 | INFORMS Journal on Computing, Vol. 0, No. 0
- An Exact Branch-Price-and-Cut Algorithm for the Unrelated Parallel Machine Scheduling Problem
  Yang Yu,
  Xiaolong Li,
  Roberto Baldacci,
  Zhiqiao Wu,
  Wei Sun,
  Jiafu Tang,
  Han Zhu
  9 June 2026 | INFORMS Journal on Computing, Vol. 0, No. 0
- On solving a share-a-ride problem with forbidden passenger detours
  Computers & Operations Research, Vol. 190
- The service-centric Vehicle Routing Problem with Crowdshipping
  European Journal of Operational Research, Vol. 331, No. 2
- Branch-price-and-cut for the production routing problem with time windows
  16 March 2026 | OR Spectrum, Vol. 48, No. 2
- Branch-price-and-cut for the vehicle routing problem with simultaneous delivery and pickup, time windows, and load-dependent cost
  European Journal of Operational Research, Vol. 59
- RouteOpt: An Open-Source Modular Exact Solver for Vehicle Routing Problems
  Zhengzhong You,
  Yu Yang
  21 May 2026 | INFORMS Journal on Computing, Vol. 0, No. 0
- An Exact Algorithm for the Vehicle Routing Problem with Time Windows and Perishable Products
  Selin Hülagü,
  Claudio Ciancio,
  Said Dabia,
  Wout Dullaert
  4 May 2026 | Transportation Science, Vol. 0, No. 0
- A tabu search for the edge set vehicle routing problem with time windows with and without waiting
  European Journal of Operational Research, Vol. 218
- Follow the Sun and Catch the Wind: A Spatio-Temporal GNN-DRL Routing Framework for Carbon-Neutral Geo-Distributed Data Centers
- Beyond fifty years of vehicle routing: Insights into the history and the future
  European Journal of Operational Research, Vol. 330, No. 2
- A hybrid swarm intelligence and dynamic programming framework for active-imaging satellite mission planning problem
  Swarm and Evolutionary Computation, Vol. 104
- Subset‐Row Inequalities and Unreachability in Path‐Based Formulations for Vehicle Routing and Scheduling Problems
  22 October 2025 | Networks, Vol. 87, No. 2
- Two-Stage Learning to Branch in Branch-Price-and-Cut Algorithms for Solving Vehicle Routing Problems Exactly
  Zhengzhong You,
  Yu Yang,
  Xinshang Wang,
  Wotao Yin
  24 February 2026 | Operations Research, Vol. 0, No. 0
- A comparative study of branch‐and‐price algorithms for vehicle routing with time windows and waiting time costs
  9 February 2026 | International Transactions in Operational Research, Vol. 26
- The periodic vehicle routing problem with multi-day trips
  Transportation Research Part E: Logistics and Transportation Review, Vol. 206
- Vehicle Routing Problem With Time Windows—New Valid Inequalities From Polar Duality
  15 September 2025 | Networks, Vol. 87, No. 1
- Cluster Branching for Vehicle Routing Problems
  João Marcos Pereira Silva,
  Eduardo Uchoa,
  Anand Subramanian
  11 November 2025 | INFORMS Journal on Computing, Vol. 0, No. 0
- An Open Visualization Platform for Route Optimize Solvers for Real-World Logistics System
- Branch-and-cut-and-price for agile earth observation satellite scheduling
  European Journal of Operational Research, Vol. 326, No. 3
- Resource-robust valid inequalities for vehicle routing and related problems
  Operations Research Letters, Vol. 63
- An iterated local search based approach for a real rich vehicle routing problem with time windows
  Computers & Industrial Engineering, Vol. 208
- Robust coordinated path planning for unmanned aerial vehicles and unmanned surface vehicles in maritime monitoring with travel time uncertainty
  Transportation Research Part B: Methodological, Vol. 199
- An exact algorithm for a mobile production vehicle routing problem
  Transportation Research Part E: Logistics and Transportation Review, Vol. 201
- Exact algorithms for routing electric autonomous mobile robots in intralogistics
  European Journal of Operational Research, Vol. 323, No. 3
- DeLuxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods
  Yu Yang
  27 November 2024 | Operations Research, Vol. 73, No. 3
- Modular Autonomous Electric Vehicle scheduling for demand-responsive transit services with modular charging strategy
  Advanced Engineering Informatics, Vol. 65
- Optimizing carbon emissions in green logistics for time-dependent routing
  Transportation Research Part B: Methodological, Vol. 192
- Integrated multi-plant collaborative production, inventory, and hub–spoke delivery of make-to-order products
  30 November 2023 | IISE Transactions, Vol. 57, No. 1
- Hybrid Genetic Search for Dynamic Vehicle Routing with Time Windows
  23 July 2025
- Exact solution of location–routing problems with heterogeneous fleet and weight-based carbon emissions
  Transportation Research Part E: Logistics and Transportation Review, Vol. 193
- Partial dominance in branch-price-and-cut algorithms for vehicle routing and scheduling problems with a single-segment tradeoff
  26 June 2024 | OR Spectrum, Vol. 46, No. 4
- Path Planning Algorithm for UAV Based Water Quality Monitoring
- Using public transport in a 2-echelon last-mile delivery network
  European Journal of Operational Research, Vol. 317, No. 3
- An enhanced exact algorithm for the multi-trip vehicle routing problem with time windows and capacitated unloading station
  Computers & Operations Research, Vol. 168
- LCEVES : A locally constrained evolutionary algorithm for vehicle evacuation scheduling under urban waterlogging risk
  7 June 2024 | Transactions in GIS, Vol. 28, No. 5
- VRPSolverEasy: A Python Library for the Exact Solution of a Rich Vehicle Routing Problem
  Najib Errami,
  Eduardo Queiroga,
  Ruslan Sadykov,
  Eduardo Uchoa
  28 December 2023 | INFORMS Journal on Computing, Vol. 36, No. 4
- Generalized Riskiness Index in Vehicle Routing Under Uncertain Travel Times: Formulations, Properties, and Exact Solution Framework
  Zhenzhen Zhang,
  Yu Zhang,
  Roberto Baldacci
  13 May 2024 | Transportation Science, Vol. 58, No. 4
- Delay-resistant robust vehicle routing with heterogeneous time windows
  Computers & Operations Research, Vol. 164
- Drone routing problem with swarm synchronization
  European Journal of Operational Research, Vol. 314, No. 2
- A unified exact approach for a broad class of vehicle routing problems with simultaneous pickup and delivery
  Computers & Operations Research, Vol. 162
- Continuity-skill-restricted scheduling and routing problem: Formulation, optimization and implications
  28 June 2023 | IISE Transactions, Vol. 56, No. 2
- Resource-Window Reduction by Reduced Costs in Path-Based Formulations for Routing and Scheduling Problems
  Nicola Bianchessi,
  Timo Gschwind,
  Stefan Irnich
  4 September 2023 | INFORMS Journal on Computing, Vol. 36, No. 1
- Estimating the marginal cost to deliver to individual customers
  9 January 2023 | Optimization and Engineering, Vol. 24, No. 4
- An Exact Method for a First-Mile Ridesharing Problem
  Sihan Wang,
  Roberto Baldacci,
  Yang Yu,
  Yu Zhang,
  Jiafu Tang,
  Xinggang Luo,
  Wei Sun
  29 September 2023 | Transportation Science, Vol. 57, No. 6
- A branch-and-price-and-cut algorithm for time-dependent pollution routing problem
  Transportation Research Part C: Emerging Technologies, Vol. 156
- Dynamics between warehouse operations and vehicle routing
  1 November 2023 | Production and Operations Management, Vol. 32, No. 11
- Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows
  European Journal of Operational Research, Vol. 310, No. 1
- Planning robust drone-truck delivery routes under road traffic uncertainty
  European Journal of Operational Research, Vol. 309, No. 3
- An exact method for vessel emission monitoring with a ship-deployed heterogeneous fleet of drones
  Transportation Research Part C: Emerging Technologies, Vol. 153
- Solving the capacitated vehicle routing problem with time windows via graph convolutional network assisted tree search and quantum-inspired computing
  22 June 2023 | Frontiers in Applied Mathematics and Statistics, Vol. 9
- A Bibliometric Visualized Analysis and Classification of Vehicle Routing Problem Research
  29 April 2023 | Sustainability, Vol. 15, No. 9
- New exact and heuristic algorithms to solve the prize-collecting job sequencing problem with one common and multiple secondary resources
  European Journal of Operational Research, Vol. 306, No. 1
- The Fragility-Constrained Vehicle Routing Problem with Time Windows
  Clément Altman,
  Guy Desaulniers,
  Fausto Errico
  22 September 2022 | Transportation Science, Vol. 57, No. 2
- Robust drone selective routing in humanitarian transportation network assessment
  European Journal of Operational Research, Vol. 305, No. 1
- Branch-Cut-and-Price for the Time-Dependent Green Vehicle Routing Problem with Time Windows
  Yiming Liu,
  Yang Yu,
  Yu Zhang,
  Roberto Baldacci,
  Jiafu Tang,
  Xinggang Luo,
  Wei Sun
  25 July 2022 | INFORMS Journal on Computing, Vol. 35, No. 1
- A New Exact Algorithm for Single-Commodity Vehicle Routing with Split Pickups and Deliveries
  Jiliu Li,
  Zhixing Luo,
  Roberto Baldacci,
  Hu Qin,
  Zhou Xu
  18 November 2022 | INFORMS Journal on Computing, Vol. 35, No. 1
- Partial Dominance in Branch-Price-and-Cut for the Basic Multicompartment Vehicle-Routing Problem
  Katrin Heßler,
  Stefan Irnich
  1 December 2022 | INFORMS Journal on Computing, Vol. 35, No. 1
- An Exact Price-Cut-and-Enumerate Method for the Capacitated Multitrip Vehicle Routing Problem with Time Windows
  Yu Yang
  25 July 2022 | Transportation Science, Vol. 57, No. 1
- New Neighborhood Strategies for the Bi-objective Vehicle Routing Problem with Time Windows
  23 February 2023
- Improving MOEA/D with Knowledge Discovery. Application to a Bi-objective Routing Problem
  9 March 2023
- Deluxing: Deep Lagrangian Underestimate Fixing for Column-Generation-Based Exact Methods
  1 January 2023 | SSRN Electronic Journal, Vol. 75
- Two-Stage Learning to Branch in Branch-Price-And-Cut Algorithms for Solving Vehicle Routing Problems Exactly
  1 January 2023 | SSRN Electronic Journal, Vol. 29
- Approximate solution of the shortest path problem with resource constraints and applications to vehicle routing problems
  Electronic Research Archive, Vol. 31, No. 2
- Robust vehicle routing under uncertainty via branch-price-and-cut
  12 September 2021 | Optimization and Engineering, Vol. 23, No. 4
- Joint routing of conventional and range-extended electric vehicles in a large metropolitan network
  Transportation Research Part C: Emerging Technologies, Vol. 144
- Solving real urban VRPTW instances by applying a Branch-Cut-and-Price via VRPsolver
- The pickup and delivery problem with time windows, multiple stacks, and handling operations
  European Journal of Operational Research, Vol. 301, No. 2
- Branch-and-Price-and-Cut for the Heterogeneous Fleet and Multi-Depot Static Bike Rebalancing Problem with Split Load
  31 August 2022 | Sustainability, Vol. 14, No. 17
- Branch-and-Price Approaches for Real-Time Vehicle Routing with Picking, Loading, and Soft Time Windows
  Martin Wölck,
  Stephan Meisel
  18 February 2022 | INFORMS Journal on Computing, Vol. 34, No. 4
- A Repeated Route-then-Schedule Approach to Coordinated Vehicle Platooning: Algorithms, Valid Inequalities and Computation
  Fengqiao Luo,
  Jeffrey Larson
  16 August 2021 | Operations Research, Vol. 70, No. 4
- Scheduling heterogeneous delivery tasks on a mixed logistics platform
  European Journal of Operational Research, Vol. 298, No. 2
- Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization
  Miao Yu,
  Viswanath Nagarajan,
  Siqian Shen
  10 November 2021 | INFORMS Journal on Computing, Vol. 34, No. 2
- A Simulated Annealing Algorithm for the Vehicle Routing Problem With Parcel Lockers
  IEEE Access, Vol. 10
- Joint Routing of Conventional and Range-Extended Electric Vehicles in a Large Metropolitan Network
  SSRN Electronic Journal, Vol. 64
- An Exact Method for the Daily Package Shipment Problem with Outsourcing
  SSRN Electronic Journal, Vol. 10
- Coordinated Vehicle Platooning with Fixed Routes: Adaptive Time Discretization, Strengthened Formulations and Approximation Algorithms
  SSRN Electronic Journal, Vol. 45
- Deep reinforcement learning algorithm for solving material emergency dispatching problem
  Mathematical Biosciences and Engineering, Vol. 19, No. 11
- The last-mile vehicle routing problem with delivery options
  21 June 2021 | OR Spectrum, Vol. 43, No. 4
- The Vehicle Routing Problem: State-of-the-Art Classification and Review
  2 November 2021 | Applied Sciences, Vol. 11, No. 21
- A machine learning-based branch and price algorithm for a sampled vehicle routing problem
  30 January 2021 | OR Spectrum, Vol. 43, No. 3
- Selective arc‐ng pricing for vehicle routing
  5 December 2020 | International Transactions in Operational Research, Vol. 28, No. 5
- Machine-Learning–Based Column Selection for Column Generation
  Mouad Morabit,
  Guy Desaulniers,
  Andrea Lodi
  30 June 2021 | Transportation Science, Vol. 55, No. 4
- Solving Bin Packing Problems Using VRPSolver Models
  8 April 2021 | Operations Research Forum, Vol. 2, No. 2
- A Hybrid Algorithm for the Drilling Rig Routing Problem
  1 October 2021 | Journal of Applied and Industrial Mathematics, Vol. 15, No. 2
- Robust Data-Driven Vehicle Routing with Time Windows
  Yu Zhang,
  Zhenzhen Zhang,
  Andrew Lim,
  Melvyn Sim
  24 February 2021 | Operations Research, Vol. 69, No. 2
- Branch-and-Price for a Multi-attribute Technician Routing and Scheduling Problem
  2 January 2021 | Operations Research Forum, Vol. 2, No. 1
- The Migratory Beekeeping Routing Problem: Model and an Exact Algorithm
  Zu-Jun Ma,
  Fei Yang,
  Ying Dai,
  Zuo-Jun Max Shen
  7 July 2020 | INFORMS Journal on Computing, Vol. 33, No. 1
- A Bucket Graph–Based Labeling Algorithm with Application to Vehicle Routing
  Ruslan Sadykov,
  Eduardo Uchoa,
  Artur Pessoa
  5 October 2020 | Transportation Science, Vol. 55, No. 1
- Accurate Tracking, Collision Detection, and Optimal Scheduling of Airport Ground Support Equipment
  IEEE Internet of Things Journal, Vol. 8, No. 1
- A Column Generation-Based Heuristic for the Split Delivery Vehicle Routing Problem with Time Windows
  29 September 2020 | SN Operations Research Forum, Vol. 1, No. 4
- A generic exact solver for vehicle routing and related problems
  25 June 2020 | Mathematical Programming, Vol. 183, No. 1-2
- An integrated route, temperature and humidity planning problem for the distribution of perishable products
  Computers & Industrial Engineering, Vol. 147
- On the exact solution of a large class of parallel machine scheduling problems
  3 February 2020 | Journal of Scheduling, Vol. 23, No. 4
- Linear edge costs and labeling algorithms: The case of the time‐dependent vehicle routing problem with time windows
  19 March 2020 | Networks, Vol. 76, No. 1
- Industrial and tramp ship routing problems: Closing the gap for real-scale instances
  European Journal of Operational Research, Vol. 283, No. 3
- The new optimization algorithm for the vehicle routing problem with time windows using multi-objective discrete learnable evolution model
  12 September 2019 | Soft Computing, Vol. 24, No. 9
- Optimal Solution of Vehicle Routing Problems with Fractional Objective Function
  Roberto Baldacci,
  Andrew Lim,
  Emiliano Traversi,
  Roberto Wolfler Calvo
  5 March 2020 | Transportation Science, Vol. 54, No. 2
- Research on Optimization of Electric Vehicle Routing Problem With Time Window
  IEEE Access, Vol. 8
- A Two-Phase Distributed Ruin-and-Recreate Genetic Algorithm for Solving the Vehicle Routing Problem With Time Windows
  IEEE Access, Vol. 8
- Comparative Analysis of Capacitated Arc Routing Formulations for Designing a New Branch-Cut-and-Price Algorithm
  Diego Pecin,
  Eduardo Uchoa
  20 September 2019 | Transportation Science, Vol. 53, No. 6
- Revised Pulse Algorithm for Elementary Shortest Path Problem with Resource Constraints
- A rollout algorithm for the resource constrained elementary shortest path problem
  4 December 2018 | Optimization Methods and Software, Vol. 34, No. 5
- Cover Inequalities for a Vehicle Routing Problem with Time Windows and Shifts
  Said Dabia,
  Stefan Ropke,
  Tom van Woensel
  27 August 2019 | Transportation Science, Vol. 53, No. 5
- Branch-and-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs
  Qie He,
  Stefan Irnich,
  Yongjia Song
  6 August 2019 | Transportation Science, Vol. 53, No. 5
- Exact and Heuristic Solution of the Consistent Vehicle-Routing Problem
  Dominik Goeke,
  Roberto Roberti,
  Michael Schneider
  28 June 2019 | Transportation Science, Vol. 53, No. 4
- Exact Branch-Price-and-Cut Algorithms for Vehicle Routing
  Luciano Costa,
  Claudio Contardo,
  Guy Desaulniers
  28 June 2019 | Transportation Science, Vol. 53, No. 4
- The Robust Vehicle Routing Problem with Time Windows: Compact Formulation and Branch-Price-and-Cut Method
  Pedro Munari,
  Alfredo Moreno,
  Jonathan De La Vega,
  Douglas Alem,
  Jacek Gondzio,
  Reinaldo Morabito
  24 June 2019 | Transportation Science, Vol. 53, No. 4
- Probabilistic Analysis of UAV Routing with Dynamically Arriving Targets
- Routing optimization with time windows under uncertainty
  23 February 2018 | Mathematical Programming, Vol. 175, No. 1-2
- SMT-LH: A New Satisfiability Modulo Theory-Based Technique for Solving Vehicle Routing Problem with Time Window Constraints
  11 January 2019 | The Computer Journal, Vol. 40
- A Generic Exact Solver for Vehicle Routing and Related Problems
  13 April 2019
- An ant colony optimization algorithm with time window constraints relaxation for solving the vehicle routing problem
  Вычислительные технологии, No. 5(23)
- The Mobile Charging Vehicle Routing Problem with Time Windows and Recharging Services
  Computational Intelligence and Neuroscience, Vol. 2018
- A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen
  22 May 2018 | TOP, Vol. 26, No. 3
- Enhanced Branch-Cut-and-Price algorithm for heterogeneous fleet vehicle routing problems
  European Journal of Operational Research, Vol. 270, No. 2
- On the complete set packing and set partitioning polytopes: Properties and rank 1 facets
  Operations Research Letters, Vol. 46, No. 4
- A branch-and-price algorithm for the Minimum Latency Problem
  Computers & Operations Research, Vol. 93
- An Evolutionary Scatter Search Particle Swarm Optimization Algorithm for the Vehicle Routing Problem With Time Windows
  IEEE Access, Vol. 6

cover image INFORMS Journal on Computing

Volume 29, Issue 3

Summer 2017

Pages 377-580

Article Information

Supplemental Material

Metrics

Information

Received:May 26, 2016
Accepted:November 07, 2016
Published Online:June 26, 2017

Cite as

Diego Pecin, Claudio Contardo, Guy Desaulniers, Eduardo Uchoa (2017) New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows. INFORMS Journal on Computing 29(3):489-502.

https://doi.org/10.1287/ijoc.2016.0744

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows

Supplemental Material

Volume 29, Issue 3

Article Information

Supplemental Material

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News