Modeling and solving the mixed capacitated general routing problem

被引：31

作者：

Bosco, Adamo ^{[1
]}

Lagana, Demetrio ^{[1
]}

Musmanno, Roberto ^{[1
]}

Vocaturo, Francesca ^{[2
]}

机构：

[1] Univ Calabria, Dipartimento Elettron Informat & Sistemist, I-87036 Arcavacata Di Rende, CS, Italy

[2] Univ Calabria, Dipartimento Econ & Stat, I-87036 Arcavacata Di Rende, CS, Italy

来源：

OPTIMIZATION LETTERS | 2013年 / 7卷 / 07期

关键词：

Routing problem; Mixed graph; Relaxation; Separation algorithm; CUTTING PLANE ALGORITHM; CUT ALGORITHM; POLYHEDRON; INEQUALITIES; NETWORKS; FACETS; BRANCH;

D O I：

10.1007/s11590-012-0552-y

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We tackle the mixed capacitated general routing problem (MCGRP) which generalizes many other routing problems. We propose an integer programming model for the MCGRP and extend some inequalities originally introduced for the capacitated arc routing problem (CARP). Identification procedures for these inequalities and for some relaxed constraints are also discussed. Finally, we describe a branch and cut algorithm including the identification procedures and present computational experiments over instances derived from the CARP.

引用

页码：1451 / 1469

页数：19

共 28 条

[1] A cutting plane algorithm for the capacitated arc routing problem [J].