期刊
NETWORKS
卷 58, 期 4, 页码 273-289出版社
WILEY-BLACKWELL
DOI: 10.1002/net.20472
关键词
vehicle routing with time windows; temporal dependency; generalized precedence constraints; time-window branching; relaxation; column generation; branch-and-price; branch-and-cut-and-price; set partitioning; set covering; integer programming
资金
- Danish Ministry of Science, Technology and Innovation
In this article, we formulate the vehicle routing problem with time windows and temporal dependencies. The problem is an extension of the well studied vehicle routing problem with time windows. In addition to the usual constraints, a scheduled time of one visit may restrain the scheduling options of other visits. Special cases of temporal dependencies are synchronization and precedence constraints. Two compact formulations of the problem are introduced and the Dantzig-Wolfe decompositions of these formulations are presented to allow for a column generation-based solution approach. Temporal dependencies are modeled by generalized precedence constraints. Four different master problem formulations are proposed and it is shown that the formulations can be ranked according to the tightness with which they describe the solution space. A tailored time window branching is used to enforce feasibility on the relaxed master problems. Finally, a computational study is performed to quantitatively reveal strengths and weaknesses of the proposed formulations. It is concluded that, depending on the problem at hand, the best performance is achieved either by relaxing the generalized precedence constraints in the master problem, or by using a time-indexed model, where generalized precedence constraints are added as cuts when they become severely violated. (C) 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 58(4), 273-289 2011
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据