.png){kind=icon}
.png){kind=icon}
Return
The capacitated minimum spanning tree problem with arc time windows
.png){kind=icon}
PRE
AI
DOI：10.1016/j.eswa.2021.114859.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider a new variant of the minimum spanning tree problem, where time windows are associated with the arcs of the underlying graph and capacities relate to the maximum number of vertices that subtrees may incorporate. The problem is referred to as the Capacitated Minimum Spanning Tree with Arc Time Windows (CMSTP_ATW) and emerges in routing situations with flow disruptions across road segments. We devise a Mixed Integer Programming (MIP) formulation to model the problem, which can be solved using CPLEX. To examine the quality of the solutions obtained, we convert the data sets of Solomon (1987) to appropriately capture CMSTP_ATW instances and provide results for the problems with 25, 50 and 100 vertices. Furthermore, we compare the CPLEX built-in heuristic that determines the initial integer solution for the CMSPT_ATW, vis-a-vis a greedy heuristic we have developed that offers high quality solutions in short computational times for the large size test problems. Experimental results show that there is a strong negative correlation between the GAP of CPLEX and the total number of iterations in one-hour performance time, against the no or positive correlation between the GAP of CPLEX and the initial iterations. Finally, we modify the MIP by adding parts of the solution derived, using the greedy heuristic, in the set of problem constraints, and observe that the CPLEX results for the CMSTP_ATW are in general improved, offering evidence that it is a promising solution approach.
Keywords:
Capacitated Minimum Spanning Tree
Arc Time Windows
Mixed Integer Programming Formulation
Heuristics
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
7.5
Papers:
2.9W
Citations:
10.2W
Organization
No organization information available