A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows

Operations Research - Tập 46 Số 3 - Trang 330-335 - 1998
Michel Gendreau1, Alain Hertz2, Gilbert Laporte3, Mihnea Stan4
1Université de Montrél, Montréal, Québec, Canada
2École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
3École des Hautes Études Commerciales, Montreál, Québec, Canada
4Delta Technology, Atlanta, Georgia

Tóm tắt

This article describes a generalized insertion heuristic for the Traveling Salesman Problem with Time Windows in which the objective is the minimization of travel times. The algorithm gradually builds a route by inserting at each step a vertex in its neighbourhood on the current route, and performing a local reoptimization. This is done while checking the feasibility of the remaining part of the route. Backtracking is sometimes necessary. Once a feasible route has been determined, an attempt is made to improve it by applying a post-optimization phase based on the successive removal and reinsertion of all vertices. Tests performed on 375 instances indicate that the proposed heuristic compares very well with alternative methods and very often produces optimal or near-optimal solutions.

Từ khóa


Tài liệu tham khảo

10.1287/opre.31.5.938

Carter M. W., 1996, INFOR., 34, 290

10.1002/net.3230110207

10.1287/opre.40.2.342

10.1080/01966324.1986.10737198

Desrosiers J., 1995, Handbooks in Operations Research and Management Science, 35

10.1287/opre.43.2.367

10.1287/opre.40.6.1086

10.1287/mnsc.40.10.1276

Kohl N. Exact methods for time constrained routing and related scheduling problems. (1995) . Ph.D. dissertation, IMM-DTU Technical University of Denmark, Denmark

10.1002/net.3230230706

10.1287/ijoc.8.2.158

10.1287/trsc.14.2.130

10.1287/trsc.17.3.351

10.1287/ijoc.8.2.134

10.1007/BF02022044

10.1287/opre.35.2.254

Thông tin
Thông tin xuất bản

Operations Research

Tập 46 Số 3

330-335

Thông tin tác giả