A parallel insertion heuristic for vehicle routing with side constraints

Statistica NeerlandicaPublished 1 September 1990Open access

Martin Savelsbergh

DOI10.1111/j.1467-9574.1990.tb01278.x

Citations9

TL;DR

This paper discusses some of the strong and weak points of this generalized assignment heuristic, and takes its basic ideas to develop a new parallel insertion heuristic for the vehicle routing and scheduling problem that is better able to handle various side constraints.

Abstract

In the early eighties, Fisher and Jaikumar developed a generalized assignment heuristic for vehicle routing problems. In this paper, we discuss some of the strong and weak points of this heuristic, and take its basic ideas to develop a new parallel insertion heuristic for the vehicle routing and scheduling problem that is better able to handle various side constraints.

Keywords

Computer ScienceEngineering

Series on software engineering and knowledge engineeringData Structures and Algorithms

2,131 Citations2003

The basis of this book is the material contained in the first six chapters of the earlier work, The Design and Analysis of Computer Algorithms, and has added material on algorithms for external storage and memory management.

NetworksA generalized assignment heuristic for vehicle routing

1,060 Citations1981Marshall L. Fisher, Ramchandran Jaikumar

This paper presents a heuristic for this problem in which an assignment of customers to vehicles is obtained by solving a generalized assignment problem with an objective function that approximates delivery cost and shows that it has outperformed the best existing heuristics on a sample of standard test problems.

European Journal of Operational ResearchVehicle routing: Methods and studies

814 Citations1989Jakob Krarup

Annals of Operations ResearchLocal search in routing problems with time windows

660 Citations1985Martin Savelsbergh

This work develops local search algorithms for routing problems with time windows based on thek-interchange concept and considers the problem of finding initial solutions.

European Journal of Operational ResearchAn efficient implementation of local search algorithms for constrained routing problems

107 Citations1990Martin Savelsbergh

This work investigates the implementation of local search algorithms for routing problems with various side constraints such as time windows on vertices and precedence relations between vertices based on the k-exchange concept and shows how this effort can be reduced to a constant.

Operations ResearchTechnical Note—An Improved Dual Based Algorithm for the Generalized Assignment Problem

84 Citations1989Monique Guignard, Moshe B. Rosenwein

An optimization algorithm is designed for the generalized assignment problem GAP that effectively solves problems with up to 500 variables and requires fewer enumeration nodes and shorter running times.