A Comparison of Traditional and Constraint-based Heuristic Methods on Vehicle Routing Problems with Side Constraints

被引：15

作者：

Kilby P. ^{[1
]}

Prosser P. ^{[2
]}

Shaw P. ^{[3
]}

机构：

[1] CSIRO MIS, Canberra, ACT 2601

[2] Department of Computer Science, University of Strathclyde, Glasgow

[3] ILOG S.A., 94253 Gentilly Cedex, BP 85

来源：

Constraints | 2000年 / 5卷 / 4期

关键词：

Construction and improvement techniques; Side constraints; Vehicle routing;

D O I：

10.1023/A:1009808327381

中图分类号：

学科分类号：

摘要：

The vehicle routing problem (VRP) is a variant of the familiar travelling salesperson problem (TSP). In the VRP we are to perform a number of visits, using a number of vehicles of limited capacity, while typically minimizing the distance travelled. VRPs can be complicated by imposing time windows or deadlines on visits, sequencing constraints between visits, and so on. In this paper, we use a constraint-based toolkit for solving vehicle routing problems to study the effect of different heuristic techniques. We investigate the performance of a number of construction and improvement techniques, and show that as the size of the solution space is decreased through addition of side constraints, certain conventional techniques fail while constraint directed techniques continue to perform acceptably. This suggests that constraint programming techniques are particularly suited to VRPs with side constraints.

引用

页码：389 / 414

页数：25

共 37 条

[1]

Applegate D., Cook W., A computational study of the job-shop scheduling problem, ORSA Journal on Computing, 3, pp. 149-156, (1991)

[2]

Baker E.K., Schaffer J.R., Solution improvement heuristics for the vehicle routing and scheduling problem with time window constraints, American Journal of Mathematical and Management Sciences, 6, 3, pp. 261-300, (1986)

[3]

Caseau Y., Laburthe F., The CLAIRE documentation, Technical Report LIENS Report 96-15, (1995)

[4]

Caseau Y., Laburthe F., Disjunctive scheduling with task intervals, Technical Report, LIENS Technical Report 95-25, (1995)

[5]

Caseau Y., Laburthe F., Solving small TSPs with constraints, Proceedings of the 14th International Conference on Logic Programming, (1997)

[6]

Caseau Y., Laburthe F., SALSA: A language for search algorithms, Proceedings of CP '98, pp. 310-324, (1998)

[7]

Cheeseman P., Kanefsky B., Taylor W.M., Where the really hard problems are, Proceedings of the 12th IJCAI, pp. 331-337, (1991)

[8]

Clarke G., Wright J., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 4, pp. 568-581, (1964)

[9]

Desrochers M., Desrosiers J., Solomon M., A new optimization algorithm for the vehicle routing problem with time windows, Operations Research, 40, 2, pp. 342-354, (1992)

[10]

Glover F.W., Laguna M., Tabu Search, (1997)

← 1 2 3 4 →