CP methods for scheduling and routing with time-dependent task costs

Kelareva E, Tierney K, Kilby P (2014)
EURO Journal on Computational Optimization 2(3): 147-194.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Kelareva, Elena; Tierney, KevinUniBi ; Kilby, Philip
Abstract / Bemerkung
A particularly difficult class of scheduling and routing problems involves an objective that is a sum of time-varying action costs, which increases the size and complexity of such problems. Solve-and-improve approaches, which find an initial solution for a simplified model and improve it using a cost function, and mixed integer programming (MIP) are often used for solving such problems. However, constraint programming (CP), particularly with lazy clause generation (LCG), has been found to be faster than MIP for some scheduling problems with time-varying action costs. In this paper, we compare CP and LCG against a solve-and-improve approach for two recently introduced problems in the area of maritime logistics with time-varying action costs: the liner shipping fleet repositioning problem (LSFRP) and the bulk port cargo throughput optimisation problem (BPCTOP). We present a novel CP model for the LSFRP, which is faster than all previous methods and outperforms a simplified automated planning model without time-varying costs. We show that a LCG solver is faster for solving the BPCTOP than a standard finite domain CP solver with a simplified model. We find that CP and LCG are effective methods for solving problems with time-dependent task costs and are worth investigating for other scheduling and routing problems that are currently being solved using MIP or solve-and-improve approaches, even when customized global constraints are not available. We also investigate a novel approach to solving the BPCTOP—converting the problem into a vehicle routing problem (VRP) and solving using an existing VRP solver.
Erscheinungsjahr
2014
Zeitschriftentitel
EURO Journal on Computational Optimization
Band
2
Ausgabe
3
Seite(n)
147-194
ISSN
2192-4406
Page URI
https://pub.uni-bielefeld.de/record/2958247

Zitieren

Kelareva E, Tierney K, Kilby P. CP methods for scheduling and routing with time-dependent task costs. EURO Journal on Computational Optimization. 2014;2(3):147-194.
Kelareva, E., Tierney, K., & Kilby, P. (2014). CP methods for scheduling and routing with time-dependent task costs. EURO Journal on Computational Optimization, 2(3), 147-194. https://doi.org/10.1007/s13675-014-0022-7
Kelareva, E., Tierney, K., and Kilby, P. (2014). CP methods for scheduling and routing with time-dependent task costs. EURO Journal on Computational Optimization 2, 147-194.
Kelareva, E., Tierney, K., & Kilby, P., 2014. CP methods for scheduling and routing with time-dependent task costs. EURO Journal on Computational Optimization, 2(3), p 147-194.
E. Kelareva, K. Tierney, and P. Kilby, “CP methods for scheduling and routing with time-dependent task costs”, EURO Journal on Computational Optimization, vol. 2, 2014, pp. 147-194.
Kelareva, E., Tierney, K., Kilby, P.: CP methods for scheduling and routing with time-dependent task costs. EURO Journal on Computational Optimization. 2, 147-194 (2014).
Kelareva, Elena, Tierney, Kevin, and Kilby, Philip. “CP methods for scheduling and routing with time-dependent task costs”. EURO Journal on Computational Optimization 2.3 (2014): 147-194.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Suchen in

Google Scholar