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

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 cos...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Elena Kelareva, Kevin Tierney, Philip Kilby
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2014
Materias:	90B06 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/3a8ac1f77196420b84472f539abc19ed
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:3a8ac1f77196420b84472f539abc19ed
record_format	dspace
spelling	oai:doaj.org-article:3a8ac1f77196420b84472f539abc19ed2021-12-02T05:00:40ZCP methods for scheduling and routing with time-dependent task costs2192-440610.1007/s13675-014-0022-7https://doaj.org/article/3a8ac1f77196420b84472f539abc19ed2014-08-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000319https://doaj.org/toc/2192-4406A 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.Elena KelarevaKevin TierneyPhilip KilbyElsevierarticle90B06Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 2, Iss 3, Pp 147-194 (2014)
institution	DOAJ
collection	DOAJ
language	EN
topic	90B06 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90B06 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Elena Kelareva Kevin Tierney Philip Kilby CP methods for scheduling and routing with time-dependent task costs
description	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.
format	article
author	Elena Kelareva Kevin Tierney Philip Kilby
author_facet	Elena Kelareva Kevin Tierney Philip Kilby
author_sort	Elena Kelareva
title	CP methods for scheduling and routing with time-dependent task costs
title_short	CP methods for scheduling and routing with time-dependent task costs
title_full	CP methods for scheduling and routing with time-dependent task costs
title_fullStr	CP methods for scheduling and routing with time-dependent task costs
title_full_unstemmed	CP methods for scheduling and routing with time-dependent task costs
title_sort	cp methods for scheduling and routing with time-dependent task costs
publisher	Elsevier
publishDate	2014
url	https://doaj.org/article/3a8ac1f77196420b84472f539abc19ed
work_keys_str_mv	AT elenakelareva cpmethodsforschedulingandroutingwithtimedependenttaskcosts AT kevintierney cpmethodsforschedulingandroutingwithtimedependenttaskcosts AT philipkilby cpmethodsforschedulingandroutingwithtimedependenttaskcosts
_version_	1718400822879977472

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

Ejemplares similares