启发式
数学
计算机科学
车辆路径问题
集合(抽象数据类型)
启发式
卡车
算法
不平等
剖切面法
多面体
布线(电子设计自动化)
数学优化
线性规划
整数规划
分支和切割
组合数学
工程类
程序设计语言
航空航天工程
数学分析
计算机网络
作者
P. Augerat,Denis Naddef,José Manuel Belenguer,Enrique Benavent,Ángel Corberán,Giovanni Rinaldi
出处
期刊:Research Report Series of IASI-CNR, Rome, Italy (ISSN: 1128-3378)
日期:1998-01-01
卷期号:495
被引量:88
摘要
The Capacitated Vehicle Routing Problem (CVRP) we consider in this paper consists in the optimization of the distribution of goods from a single depot to a given set of customers with known demand using a given number of vehicles of fixed capacity. There are many practical routing applications in the public sector such as school bus routing, pick up and mail delivery, and in the private sector such as the dispatching of delivery trucks. We present a Branch and Cut algorithm to solve the CVRP which is based in the partial polyhedral description of the corresponding polytope. The valid inequalities used in our method can ne found in Cornuejols and Harche (1993), Harche and Rinaldi (1991) and in Augerat and Pochet (1995). We concentrated mainly on the design of separation procedures for several classes of valid inequalities. The capacity constraints (generalized sub-tour eliminations inequalities) happen to play a crucial role in the development of a cutting plane algorithm for the CVRP. A large number of separation heuristics have been implemented and compared for these inequalities. There has been also implemented heuristic separation algorithms for other classes of valid inequalities that also lead to significant improvements: comb and extended comb inequalities, generalized capacity inequalities and hypo-tour inequalities. The resulting cutting plane algorithm has been applied to a set of instances taken from the literature and the lower bounds obtained are better than the ones previously known. Some branching strategies have been implemented to develop a Branch an Cut algorithm that has been able to solve large CVRP instances, some of them which had never been solved before. (authors). 32 refs., 3 figs., 10 tabs.
科研通智能强力驱动
Strongly Powered by AbleSci AI