Two exact algorithms for the distance-constrained vehicle routing problem

DOI10.1002/NET.3230140113zbMath0538.90093OpenAlexW2051369225MaRDI QIDQ3325496

Gilbert Laporte, Yves Nobert, Martin Desrochers

Publication date: 1984

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230140113

zbMATH Keywords

vehicle routingcomputational resultscutting plane methodbranch and bound methodexact algorithmsmultiple traveling salesman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (25)

Green hybrid fleets using electric vehicles: solving the heterogeneous vehicle routing problem with multiple driving ranges and loading capacities ⋮ Approximation algorithms for distance constrained vehicle routing problems ⋮ Layered graph approaches for combinatorial optimization problems ⋮ An overview of graph covering and partitioning ⋮ \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective ⋮ Using \(\ell^p\)-norms for fairness in combinatorial optimisation ⋮ The school bus problem on trees ⋮ Routing and scheduling field service operation by P-graph ⋮ The close-open mixed vehicle routing problem ⋮ The median routing problem for simultaneous planning of emergency response and non-emergency jobs ⋮ The vehicle sharing and task allocation problem: MILP formulation and a heuristic solution approach ⋮ Heuristic and exact algorithms for a min-max selective vehicle routing problem ⋮ Approximation algorithms for distance constraint sweep coverage with base stations ⋮ Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots ⋮ Exact hybrid algorithms for solving a bi-objective vehicle routing problem ⋮ Polyhedral results for a vehicle routing problem ⋮ A truck and drones model for last-mile delivery: a mathematical model and heuristic approach ⋮ A multi-start local search heuristic for the green vehicle routing problem based on a multigraph reformulation ⋮ Branch and cut methods for network optimization ⋮ The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem ⋮ A branch and bound algorithm for the capacitated vehicle routing problem ⋮ Probabilistic time-dependent vehicle routing problem ⋮ A mixed constrained (identical) vehicle routing problem for time minimisation ⋮ A branch-and-cut-and-price approach for the pickup and delivery problem with shuttle routes ⋮ A cutting plane procedure for the travelling salesman problem on road networks

Cites Work

• Unnamed Item
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Integer programming approaches to the travelling salesman problem

This page was built for publication: Two exact algorithms for the distance-constrained vehicle routing problem