What are the worst cases in constrained Last-In-First-Out pick-up and delivery problems?

作者：Urrutia Sebastian^*; de Werra Dominique

来源：European Journal of Operational Research, 2018, 270(2): 430-434.

DOI：10.1016/j.ejor.2018.04.005

• Combinatorial optimization
• Pick-up and delivery
• Permutation graphs
• Bounded chromatic number

Pick-up and delivery operations in transportation tasks are usually performed using stacks. The Last-In First -Out nature of stacks imposes restrictions to the order in which pick-ups and deliveries are performed. In this paper, we study the problem of determining the minimum number of stacks needed to perform given sequences of pick-up and delivery operations. We consider both, limited and unlimited capacity stacks and allow some transformations on the delivery route. These problems amount to computing the smallest bounded chromatic number in a family of permutation graphs. We study the worst cases of these problems.

• 出版日期2018-10-16