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.

              ||                ||
[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}
                    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.

  • $\begingroup$ Welcome to OR.SE. Are the orders pre-defined or it follows from a probability distribution function? $\endgroup$
    – A.Omidi
    Apr 6, 2022 at 5:13
  • $\begingroup$ @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 $\endgroup$
    – gbullins
    Apr 6, 2022 at 5:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – A.Omidi
    Apr 6, 2022 at 5:24
  • $\begingroup$ @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? $\endgroup$
    – gbullins
    Apr 6, 2022 at 5:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – prubin
    Apr 6, 2022 at 15:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.