0

Can the following problem be formulated as a LP/IP problem, where an agent (waiter) that has just arrived at a certain table has to decide whether to visit that table now, or skip the current table and travel to the next table, where he again decides whether to serve the second table.

                [Table1]
                   ||
                   ||
              ===================
              ||                ||
[Table4]  ====||                ||
              ||                ||====  [Table2]
              ||                ||
              ===================
                      ||  {WaiterA: 1 dishes of dishA (waiting for WaiterB, WaiterC to finish)}
                      ||  {WaiterB: 2 dishes of dishB (waiting for WaiterC to finish)}
                   [Table3]   {WaiterC: Serving 3 dishes of dishC}
                  ordered:
                    1x dishA  
                    2x dishB
                    3x dishC  
                    3x dishD
                    3x dishE

Additional details:

  1. Waiters can only travel in a loop path in the clockwise direction
  2. There can be multiple waiters traveling on the loop path
  3. Every waiter only serves 1 dish (waiterA serves only dishA)
  4. When a waiter is serving a table, another waiter can visit the same table and wait in queue for the initial waiter to finish serving
  5. A table can order multiple type of dishes at once
  6. The time taken by a waiter to serve an order at the table is proportional to the number of that dishes ordered by that table
  7. All waiters serve each quantity of their dish at the same speed
  8. All waiters travel the loop path at the same speed
  9. The distance between tables are not equal
  10. The ordered dishes can be served in any sequence
  11. There is only sufficient room for 3 waiters to be waiting (and 1 actively serving) for each table

We want to minimize the total time taken to serve all the ordered dishes.

I feel that we want to take into account

  • the demand of the current table vs. demand of other tables
  • the total number of dishes to be served by the waiters in queue at the current table
  • the time it will take to travel to the next table (or table with most demand for the dish that this waiter serves)

How can we formulate this as a LP problem, where we want to know a whether a waiter that has travelled to a table should join a queue to serve the table, or skip this table?

I am also assuming that we will solve this problem every time a waiter has arrived at a table.

Is there a problem category that this problem belongs to, such as the Traveling Salesman Problem? Looks like it shares some similarity with the TSP, but in TSP the salesman is not constrained to travel along a fixed path with a fixed direction.

gbullins
  • 9
  • 3
  • Welcome to OR.SE. Are the orders pre-defined or it follows from a probability distribution function? – A.Omidi Apr 06 '22 at 05:13
  • @A.Omidi Thank you for the welcome! I think we can assume that for each table, the average number of orders per dish to be $2.5$. And each table orders an average of $5$ different types of dishes – gbullins Apr 06 '22 at 05:16
  • 1
    thanks for clarifying. I think instead of using mathematical formulations, e.g. LP, MIP, etc, you can already use a discrete simulation technique to solve such a problem. As in your problem you have faced some queues, it would be better something like this can be interpreted as a simulation model. – A.Omidi Apr 06 '22 at 05:24
  • @A.Omidi Just did a quick search on DES. After creating the DES simulation model, do we still use LP to optimize for minimal costs? Also, this this problem still solvable using LP/MIP? If so, is LP/MIP faster or is DES faster to arriving at a "good enough" solution? – gbullins Apr 06 '22 at 05:46
  • Also i think the orders are pre-defined, as in we know the exact orders at the time when we need to solve for a solution (serve the current table, or skip). Not sure if this changes things – gbullins Apr 06 '22 at 05:50
  • DES is one of the optimization methods. It develops to solve complex problems in which other methods like LP/MIP/etc, might not solve the problem in an efficient manner. As your problem contains queues, I think MILP is not the best one. – A.Omidi Apr 06 '22 at 06:00
  • Also, you can combine DES with a MILP for making a better solution. – A.Omidi Apr 06 '22 at 06:01
  • 1
    Is there any concern about the time interval from first to last dish being served at a specific table? In real life, giving one person their food and then delaying a long time before bringing the rest of the food will result in unhappy customers: either the first person's food goes cold while they wait, or everyone else watches the first person eat. – prubin Apr 06 '22 at 15:23
  • Regarding DES, I don't think you need to combine it with an optimization model. You want to develop a simple set of rules for waiters: wait if these conditions all hold, move on if not. You can use as DES model to test various rules and see which performs best. – prubin Apr 06 '22 at 15:25
  • @prubin Good suggestion! According to Warren Powell, such rules would be classified as policy function approximation. However, there are different strategy classes that one might try out (CFA, VFA, DLA). Please see my answer to another question that shortly explains these three other classes: https://or.stackexchange.com/a/7713/3464. To come back to your question: It is a sequential decision problem which is usually modeled as Markov decision process (MDP). – PeterD Apr 06 '22 at 19:16
  • @Pedrinho That general framework might be appropriate, but I don't think this would be a Markov decision process because I don't think the right things are "memoryless". Service time per dish seems to be constant, and the number of dishes wouldn't be Poisson unless there were some serious gluttons at the tables. :-) – prubin Apr 06 '22 at 20:17
  • @prubin This is true. A customer's ordering is dependent (or should be at least ;) ) on his past orderings. This would then relate to a "higher-order Markov model". These can be transformed into first-order Markov models or memoryless models by including additional information (e.g. how much a customer already ordered) into the state. – PeterD Apr 06 '22 at 21:01

0 Answers0