Multistars, partial multistars and the capacitated vehicle routing problem

DOI10.1007/S10107-002-0336-8zbMath1023.90073OpenAlexW2074533831WikidataQ57702374 ScholiaQ57702374MaRDI QIDQ1396812

Jens Lysgaard, Richard W. Eglese, Adam N. Letchford

Publication date: 13 July 2003

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-002-0336-8

zbMATH Keywords

vehicle routingcutting planesvalid inequalities

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27) Traffic problems in operations research (90B20)

Related Items (33)

New Families of Valid Inequalities for the Two-Echelon Vehicle Routing Problem ⋮ Balanced vehicle routing: polyhedral analysis and branch-and-cut algorithm ⋮ The periodic vehicle routing problem with driver consistency ⋮ Optimal capacitated ring trees ⋮ Stronger multi-commodity flow formulations of the capacitated vehicle routing problem ⋮ New techniques for cost sharing in combinatorial optimization games ⋮ A branch-and-cut algorithm for the preemptive swapping problem ⋮ A branch-and-cut algorithm for the hub location and routing problem ⋮ Reverse multistar inequalities and vehicle routing problems with a lower bound on the number of customers per route ⋮ New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems ⋮ Valid inequalities and extended formulations for lot-sizing and scheduling problem with sequence-dependent setups ⋮ Numerically Safe Lower Bounds for the Capacitated Vehicle Routing Problem ⋮ Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem ⋮ Recent advances in vehicle routing exact algorithms ⋮ Polynomial-time separation of enhanced reverse multistar inequalities ⋮ Heuristic and exact algorithms for the multi-pile vehicle routing problem ⋮ An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts ⋮ Combined route capacity and route length models for unit demand vehicle routing problems ⋮ Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems ⋮ The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time ⋮ A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints ⋮ Exact algorithms for routing problems under vehicle capacity constraints ⋮ Minimum makespan vehicle routing problem with compatibility constraints ⋮ Formulations and valid inequalities for the heterogeneous vehicle routing problem ⋮ Unnamed Item ⋮ Robust branch-and-cut-and-price for the capacitated vehicle routing problem ⋮ A branch‐and‐cut algorithm for the nonpreemptive swapping problem ⋮ Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs ⋮ Capacitated ring arborescence problems with profits ⋮ Facets and valid inequalities for the time-dependent travelling salesman problem ⋮ Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm ⋮ A branch-and-cut algorithm for the capacitated profitable tour problem ⋮ Projection results for vehicle routing

Uses Software

• TSPLIB
• CVRPSP

This page was built for publication: Multistars, partial multistars and the capacitated vehicle routing problem