CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Comparing MILP, CP, and A* for Multiple Stacker Crane Scheduling

Fredrik Hagebring (Institutionen för signaler och system, Automation) ; Oskar Wigström (Institutionen för signaler och system, Automation) ; Bengt Lennartson (Institutionen för signaler och system, Automation) ; S. I. Ware ; R. Su
Proc. 13th International Workshop on Discrete Event Systems (WODES’16), Xi’an, China, May (1550-5227). p. 63-70. (2016)
[Konferensbidrag, refereegranskat]

This paper describes an optimisation model for the scheduling of a system consisting of three stacker cranes that are restricted to the same track. To improve the efficiency of the solution methods, a novel simplification of the model is presented, which has a low impact on the quality of the solution but greatly decreases its complexity. This model is then used to benchmark several popular solution methods, including both optimal and approximate methods. Some are based on monolithic models, whereas others solve the problem in phases by using sub-problem formulations. The result presented in this paper shows that evaluated solution methods have complementary strengths and weaknesses. Constraint Programming (CP) is very efficient on small scale problems, while Mixed Integer Linear Programming (MILP) scales much better when the number of movement orders increases. However, none of these methods are able to solve large instances of the problem to optimality. To handle the complexity of the problem, approximate solution methods are the only viable option. In this paper we show that promising results can be obtained even with simple methods using well known search algorithms such as A* and Tabu-search. However, preliminary results on more advanced search algorithms show that further improvements may be achieved, allowing the solution of very large problem instances.

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2016-10-14. Senast ändrad 2017-01-20.
CPL Pubid: 243392


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för signaler och system, Automation (2005-2017)


Hållbar utveckling
Robotteknik och automation

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:

Energy efficient multi-robot coordination