A logic based Benders' approach to the concrete delivery problem

J. Kinable; M. Trick

doi:10.1007/978-3-319-07046-9_13

A logic based Benders' approach to the concrete delivery problem

J. Kinable
, M. Trick

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

Abstract

This work presents an exact Logic Based Benders' decomposition for the Concrete Delivery Problem (CDP). The CDP is a complex, real world optimization problem involving the allocation and distribution of concrete to construction sites. The key scheduling issue for the CDP is the need for successive deliveries to a site to be sufficiently close in time. We decompose the CDP into a master problem and a subproblem. Based on a number of problem characteristics such as the availability of vehicles, geographical orientation of the customers and production centers, as well as the customers' demand for concrete, the master problem allocates concrete to customers. Next, the subproblem attempts to construct a feasible schedule, meeting all the routing and scheduling constraints. Infeasibilities in the schedule are communicated back to the master problem via a number of combinatorial inequalities (Benders' cuts). The master problem is solved through a Mixed Integer Programming approach, whereas the subproblem is solved via a Constraint Programming model and a dedicated scheduling heuristic. Experiments are conducted on a large number of problem instances, and compared against other exact methods presented in related literature. This algorithm is capable of solving a number of previously unsolved benchmark instances to optimality and can improve the bounds for many other instances.

Original language	English
Title of host publication	Integration of AI and OR Techniques in Constraint Programming
Subtitle of host publication	11th International Conference, CPAIOR 2014, Cork, Ireland, May 19-23, 2014. Proceedings
Editors	H. Simonis
Place of Publication	Dordrecht
Publisher	Springer
Pages	176-192
Number of pages	17
ISBN (Electronic)	978-3-319-07046-9
ISBN (Print)	978-3-319-07045-2
DOIs	https://doi.org/10.1007/978-3-319-07046-9_13
Publication status	Published - 2014
Externally published	Yes
Event	11th International Conference on the Integration of Artificial Intelligence and Operations ResearchTechniques in Constraint Programming, (CPAIOR 2014) - Cork, Ireland Duration: 19 May 2014 → 23 May 2014 Conference number: 11

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8451 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th International Conference on the Integration of Artificial Intelligence and Operations ResearchTechniques in Constraint Programming, (CPAIOR 2014)
Abbreviated title	CPAIOR 2014
Country/Territory	Ireland
City	Cork
Period	19/05/14 → 23/05/14

Keywords

Integer and Constraint Programming
Logic Based Benders' Decomposition
Scheduling
Vehicle Routing

Access to Document

10.1007/978-3-319-07046-9_13

Cite this

Kinable, J., & Trick, M. (2014). A logic based Benders' approach to the concrete delivery problem. In H. Simonis (Ed.), Integration of AI and OR Techniques in Constraint Programming : 11th International Conference, CPAIOR 2014, Cork, Ireland, May 19-23, 2014. Proceedings (pp. 176-192). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8451 LNCS). Springer. https://doi.org/10.1007/978-3-319-07046-9_13

Kinable, J. ; Trick, M. / A logic based Benders' approach to the concrete delivery problem. Integration of AI and OR Techniques in Constraint Programming : 11th International Conference, CPAIOR 2014, Cork, Ireland, May 19-23, 2014. Proceedings. editor / H. Simonis. Dordrecht : Springer, 2014. pp. 176-192 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0ab322ee9e594dc8a9028aba1a534c1c,

title = "A logic based Benders' approach to the concrete delivery problem",

abstract = "This work presents an exact Logic Based Benders' decomposition for the Concrete Delivery Problem (CDP). The CDP is a complex, real world optimization problem involving the allocation and distribution of concrete to construction sites. The key scheduling issue for the CDP is the need for successive deliveries to a site to be sufficiently close in time. We decompose the CDP into a master problem and a subproblem. Based on a number of problem characteristics such as the availability of vehicles, geographical orientation of the customers and production centers, as well as the customers' demand for concrete, the master problem allocates concrete to customers. Next, the subproblem attempts to construct a feasible schedule, meeting all the routing and scheduling constraints. Infeasibilities in the schedule are communicated back to the master problem via a number of combinatorial inequalities (Benders' cuts). The master problem is solved through a Mixed Integer Programming approach, whereas the subproblem is solved via a Constraint Programming model and a dedicated scheduling heuristic. Experiments are conducted on a large number of problem instances, and compared against other exact methods presented in related literature. This algorithm is capable of solving a number of previously unsolved benchmark instances to optimality and can improve the bounds for many other instances.",

keywords = "Integer and Constraint Programming, Logic Based Benders' Decomposition, Scheduling, Vehicle Routing",

author = "J. Kinable and M. Trick",

year = "2014",

doi = "10.1007/978-3-319-07046-9\_13",

language = "English",

isbn = "978-3-319-07045-2",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "176--192",

editor = "H. Simonis",

booktitle = "Integration of AI and OR Techniques in Constraint Programming",

address = "Germany",

note = "11th International Conference on the Integration of Artificial Intelligence and Operations ResearchTechniques in Constraint Programming, (CPAIOR 2014), CPAIOR 2014 ; Conference date: 19-05-2014 Through 23-05-2014",

}

Kinable, J & Trick, M 2014, A logic based Benders' approach to the concrete delivery problem. in H Simonis (ed.), Integration of AI and OR Techniques in Constraint Programming : 11th International Conference, CPAIOR 2014, Cork, Ireland, May 19-23, 2014. Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8451 LNCS, Springer, Dordrecht, pp. 176-192, 11th International Conference on the Integration of Artificial Intelligence and Operations ResearchTechniques in Constraint Programming, (CPAIOR 2014), Cork, Ireland, 19/05/14. https://doi.org/10.1007/978-3-319-07046-9_13

A logic based Benders' approach to the concrete delivery problem. / Kinable, J.; Trick, M.
Integration of AI and OR Techniques in Constraint Programming : 11th International Conference, CPAIOR 2014, Cork, Ireland, May 19-23, 2014. Proceedings. ed. / H. Simonis. Dordrecht: Springer, 2014. p. 176-192 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8451 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A logic based Benders' approach to the concrete delivery problem

AU - Kinable, J.

AU - Trick, M.

N1 - Conference code: 11

PY - 2014

Y1 - 2014

N2 - This work presents an exact Logic Based Benders' decomposition for the Concrete Delivery Problem (CDP). The CDP is a complex, real world optimization problem involving the allocation and distribution of concrete to construction sites. The key scheduling issue for the CDP is the need for successive deliveries to a site to be sufficiently close in time. We decompose the CDP into a master problem and a subproblem. Based on a number of problem characteristics such as the availability of vehicles, geographical orientation of the customers and production centers, as well as the customers' demand for concrete, the master problem allocates concrete to customers. Next, the subproblem attempts to construct a feasible schedule, meeting all the routing and scheduling constraints. Infeasibilities in the schedule are communicated back to the master problem via a number of combinatorial inequalities (Benders' cuts). The master problem is solved through a Mixed Integer Programming approach, whereas the subproblem is solved via a Constraint Programming model and a dedicated scheduling heuristic. Experiments are conducted on a large number of problem instances, and compared against other exact methods presented in related literature. This algorithm is capable of solving a number of previously unsolved benchmark instances to optimality and can improve the bounds for many other instances.

AB - This work presents an exact Logic Based Benders' decomposition for the Concrete Delivery Problem (CDP). The CDP is a complex, real world optimization problem involving the allocation and distribution of concrete to construction sites. The key scheduling issue for the CDP is the need for successive deliveries to a site to be sufficiently close in time. We decompose the CDP into a master problem and a subproblem. Based on a number of problem characteristics such as the availability of vehicles, geographical orientation of the customers and production centers, as well as the customers' demand for concrete, the master problem allocates concrete to customers. Next, the subproblem attempts to construct a feasible schedule, meeting all the routing and scheduling constraints. Infeasibilities in the schedule are communicated back to the master problem via a number of combinatorial inequalities (Benders' cuts). The master problem is solved through a Mixed Integer Programming approach, whereas the subproblem is solved via a Constraint Programming model and a dedicated scheduling heuristic. Experiments are conducted on a large number of problem instances, and compared against other exact methods presented in related literature. This algorithm is capable of solving a number of previously unsolved benchmark instances to optimality and can improve the bounds for many other instances.

KW - Integer and Constraint Programming

KW - Logic Based Benders' Decomposition

KW - Scheduling

KW - Vehicle Routing

UR - https://www.scopus.com/pages/publications/84902513149

U2 - 10.1007/978-3-319-07046-9_13

DO - 10.1007/978-3-319-07046-9_13

M3 - Conference contribution

AN - SCOPUS:84902513149

SN - 978-3-319-07045-2

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 176

EP - 192

BT - Integration of AI and OR Techniques in Constraint Programming

A2 - Simonis, H.

PB - Springer

CY - Dordrecht

T2 - 11th International Conference on the Integration of Artificial Intelligence and Operations ResearchTechniques in Constraint Programming, (CPAIOR 2014)

Y2 - 19 May 2014 through 23 May 2014

ER -

Kinable J, Trick M. A logic based Benders' approach to the concrete delivery problem. In Simonis H, editor, Integration of AI and OR Techniques in Constraint Programming : 11th International Conference, CPAIOR 2014, Cork, Ireland, May 19-23, 2014. Proceedings. Dordrecht: Springer. 2014. p. 176-192. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-07046-9_13

A logic based Benders' approach to the concrete delivery problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this