Solving permutational routing problems by population-based metaheuristics

被引：16

作者：

Bozejko, Wojciech ^{[1
]}

Wodecki, Mieczyslaw ^{[2
]}

机构：

[1] Wroclaw Univ Technol, Inst Comp Engn Control & Robot, PL-50372 Wroclaw, Poland

[2] Univ Wroclaw, Inst Comp Sci, PL-50383 Wroclaw, Poland

来源：

COMPUTERS & INDUSTRIAL ENGINEERING | 2009年 / 57卷 / 01期

关键词：

Metaheuristics; TSP; Single machine problem; TSP with due dates; TARDINESS;

D O I：

10.1016/j.cie.2008.11.022

中图分类号：

TP39 [计算机的应用];

学科分类号：

080201 [机械制造及其自动化];

摘要：

In this paper we consider two routing problems: traveling salesman problem (TSP, fundamental problem of the combinatorial optimization) and the TSP with times of traveling, times of processing and due dates where the objective is to minimize the total weighted tardiness (TSPTWT). Since problems are NP-hard in the strong sense, we propose a metaheuristic algorithm to determine a good sub-optimal solution. We present an algorithm based on the idea of researching and analyzing local optima. TSP with times of traveling, times of processing and due dates, and with the total weighted tardiness cost function is identical with the single machine total weighted tardiness problem with sequence-dependent setup times. It was possible to find the new best known solutions for 81 of 120 benchmark instances of this scheduling problem using the method proposed here. (C) 2008 Elsevier Ltd. All rights reserved

引用

页码：269 / 276

页数：8

共 20 条

[1]

CHIA YL, 2007, P 2007 INFORMS SIM S

[2]

Enhancing stochastic search performance by value-biased randomization of heuristics [J].

Cicirello, VA ;

Smith, SF .

JOURNAL OF HEURISTICS, 2005, 11 (01) :5-34

[3]

CICIRELLO VA, 2006, P 8 ANN GEN EV COMP

[4]

Meta-RaPS: a simple and effective approach for solving the traveling salesman problem [J].

DePuy, GW ;

Moraga, RJ ;

Whitehouse, GE .

TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2005, 41 (02) :115-130

[5]

DONGARRA JJ, 1994, CS8985 U TENN

[6]

A polyhedral approach to the asymmetric traveling salesman problem [J].

Fischetti, M ;

Toth, P .

MANAGEMENT SCIENCE, 1997, 43 (11) :1520-1536

[7]

Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times [J].

Gagné, C ;

Price, WL ;

Gravel, M .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2002, 53 (08) :895-906

[8]

On the convergence of Tabu Search [J].

Hanafi, S .

JOURNAL OF HEURISTICS, 2001, 7 (01) :47-58

[9]

A heuristic to minimize the total weighted tardiness with sequence-dependent setups [J].

Lee, YH ;

Bhaskaran, K ;

Pinedo, M .

IIE TRANSACTIONS, 1997, 29 (01) :45-52

[10]

Lenstra J. K., 1977, Annals of discrete mathematics, V1, P343, DOI DOI 10.1016/S0167-5060(08)70743-X

← 1 2 →