On the worst‐case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints
Author:
Abstract
We consider the vehicle routing and scheduling problem with time window constraints. Analytical results concerning the behavior of approximation methods for this problem class are derived through worst‐case analysis. For a variety of heuristics, it is shown that their worst‐case behavior on n customer problems is at least order of n for minimizing the number of vehicles used, the total distance traveled, and the total schedule time.Keywords
This publication has 8 references indexed in Scilit:
- On the worst‐case performance of some algorithms for the asymmetric traveling salesman problemNetworks, 1982
- Complexity of vehicle routing and scheduling problemsNetworks, 1981
- Worst-Case Analysis of Heuristic AlgorithmsManagement Science, 1980
- Tight bounds for christofides' traveling salesman heuristicMathematical Programming, 1978
- An Analysis of Several Heuristics for the Traveling Salesman ProblemSIAM Journal on Computing, 1977
- Evaluating a Sequential Vehicle Routing AlgorithmA I I E Transactions, 1977
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate AlgorithmsManagement Science, 1977
- A Computational Modification to the Savings Method of Vehicle SchedulingJournal of the Operational Research Society, 1970