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 条

[1]

[Anonymous], 1976, WORST CASE ANAL NEW

[2]

Applegate D., 2001, SOLUTION MIN MAX VEH

[3] Approximations for minimum and min-max vehicle routing problems [J].

Arkin, EM ;

Hassin, R ;

Levin, A .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2006, 59 (01) :1-18

[4] The multiple traveling salesman problem: an overview of formulations and solution procedures [J].

Bektas, T .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2006, 34 (03) :209-219

[5]

Bulb F., 2011, P IEEE, V99, P1482

[6]

Bulb F., 2012, SIAM J CONTROL OPTIM, V50, P419

[7] Communication constraints in the average consensus problem [J].

Carli, Ruggero ;

Fagnani, Fabio ;

Speranzon, Alberto ;

Zampieri, Sandro .

AUTOMATICA, 2008, 44 (03) :671-684

[8]

Carlsson J, 2009, FIELDS I COMMUN, V55, P31

[9] A guide to vehicle routing heuristics [J].

Cordeau, JF ;

Gendreau, M ;

Laporte, G ;

Potvin, JY ;

Semet, F .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2002, 53 (05) :512-522

[10] THE TRUCK DISPATCHING PROBLEM [J].

DANTZIG, GB ;

RAMSER, JH .

MANAGEMENT SCIENCE, 1959, 6 (01) :80-91

← 1 2 3 →