期刊
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
卷 -, 期 -, 页码 -出版社
TAYLOR & FRANCIS LTD
DOI: 10.1080/00207543.2023.2276818
关键词
Capacitated minimum spanning tree; arc time windows; mixed integer programming formulation; valid inequalities; flow costs
This paper introduces the non-unit demand capacitated minimum spanning tree problem with arc time windows and flow costs, presents a mixed integer programming formulation and valid inequalities to solve the problem, and conducts extensive computational experiments to demonstrate the positive effect of including valid inequalities in the MIP.
In this paper, we introduce the non-unit demand capacitated minimum spanning tree problem with arc time windows and flow costs. The problem is a variant of the capacitated minimum spanning tree problem with arc time windows (CMSTP_ATW). We devise a mixed integer programming (MIP) formulation to model the problem and solve it using CPLEX. Furthermore, we propose three sets of inequalities, and we prove that they are valid. These valid inequalities tighten the model and lead to better lower bounds. To examine the quality of the solutions obtained, we convert the original data sets of Solomon (1987, Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints. Operations Research 35 (2): 254-265. https://doi.org/10.1287/opre.35.2.254) to approximate the non-unit demand CMSTP_ATW instances and provide results for the problems with 100 nodes. We execute extensive computational experiments, and the results show the positive effect of the inclusion of valid inequalities in the MIP.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据