Gossip algorithms for heterogeneous multi-vehicle routing problems

被引：35

作者：

Franceschelli, Mauro ^{[1
]}

Rosa, Daniele ^{[1
]}

Seatzu, Carla ^{[1
]}

Bullo, Francesco ^{[2
]}

机构：

[1] Univ Cagliari, Dept Elect & Elect Engn, I-09124 Cagliari, Italy

[2] Univ Calif Santa Barbara, Dept Mech Engn, Santa Barbara, CA 93106 USA

来源：

NONLINEAR ANALYSIS-HYBRID SYSTEMS | 2013年 / 10卷

关键词：

Gossip algorithms; Distributed optimization; Multi-TSP; Vehicle routing; TRAVELING SALESMAN PROBLEM; APPROXIMATE ALGORITHMS;

D O I：

10.1016/j.nahs.2013.03.001

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper we address a class of heterogeneous multi-vehicle task assignment and routing problems. We propose two distributed algorithms based on gossip communication: the first algorithm is based on a local exact optimization and the second is based on a local approximate greedy heuristic. We consider the case where a set of heterogeneous tasks arbitrarily distributed in a plane has to be serviced by a set of mobile robots, each with a given movement speed and task execution speed. Our goal is to minimize the maximum execution time of robots. (c) 2013 Elsevier Ltd. All rights reserved.

引用

页码：156 / 174

页数：19

共 27 条

[11]

Few L., 1955, Mathematika, V2, P141, DOI DOI 10.1112/S0025579300000784

[12] A GENERALIZED ASSIGNMENT HEURISTIC FOR VEHICLE-ROUTING [J].

FISHER, ML ;

JAIKUMAR, R .

NETWORKS, 1981, 11 (02) :109-124

[13]

Franceschelli M., 2012, 4 IFAC C AN DES HYBR

[14] A Gossip-Based Algorithm for Discrete Consensus Over Heterogeneous Networks [J].

Franceschelli, Mauro ;

Giua, Alessandro ;

Seatzu, Carla .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2010, 55 (05) :1244-1249

[15] A TABU SEARCH HEURISTIC FOR THE VEHICLE-ROUTING PROBLEM [J].

GENDREAU, M ;

HERTZ, A ;

LAPORTE, G .

MANAGEMENT SCIENCE, 1994, 40 (10) :1276-1290

[16]

Gutin G., 2002, SERIES COMBINATORIAL, V12

[17]

Karloff H., 1989, SIAM J. Discrete Math, V2, P91, DOI DOI 10.1137/0402010

[18]

Laporte G., 2000, International Transactions in Operational Research, V7, P285, DOI 10.1111/j.1475-3995.2000.tb00200.x

[19] THE VEHICLE-ROUTING PROBLEM - AN OVERVIEW OF EXACT AND APPROXIMATE ALGORITHMS [J].

LAPORTE, G .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1992, 59 (03) :345-358

[20] THE TRAVELING SALESMAN PROBLEM - AN OVERVIEW OF EXACT AND APPROXIMATE ALGORITHMS [J].

LAPORTE, G .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1992, 59 (02) :231-247

← 1 2 3 →