Chocolate distribution problem in a classroom
Problem Statement
Optimize chocolate distribution among students by a teacher with minimum round trips between the boxes and seats.
Chocolate Boxes
- Each chocolate box has 4 sections as shown below to put 1 chocolate in each section. These are indicated as TL, TR, BR and BL.
- Available boxes with chocolates already filled.
- Above are the different types of boxes available that have chocolates already filled.
- c1 = Hersey’s Kisses
- c2 = Bournville
- c3 = Kit Kat
- c4 = Reese’s Cups
Classroom Seating Arrangements
- S1, S2, S3… Sn denotes seats.
- S1 (c1) means student at seat S1 needs chocolate c1 (Hershey’s Kisses)
- Seats with no chocolates present means students are absent for the day and no chocolates need to be distributed. i.e S17
- P1, P2, P3… Pn are different positions that teachers can stand and distribute chocolates.
Constraints
- Teacher can carry only 1 box at a time for 1 trip.
- When the teacher is standing at a position, chocolates can only be distributed as per the sections present in the chocolate box i.e. if teacher is at position P1, then S1 can get chocolate from TL section, S10 from TR, S11 from BR and S2 from BL section.
- Teacher can only position facing toward the top to the setup i.e. facing towards the “Classroom” word and cannot rotate.
Expected Solutions
Solution 1:
- The students who get chocolate with each trip are highlighted in the same color as Sr# column.
- Based on the above approach, total round trips that are required to complete the distribution on chocolates = 7. (These 7 round trips are highlighted with different colors and steps are written with same color in Sr# column)
Solution 2:
- The students who get chocolate with each trip are highlighted in the same color as Sr# column.
- Based on the above approach, total round trips that are required to complete the distribution on chocolates = 9.
Based on the number of round trips for each solution, Solution 1 is a more optimized approach.
We are looking for some guidance on implementing and solving using quantum computation.
Comments
Hello,
It looks like you have a very well-formulated problem!
I would be more than happy to help guide you in the right direction to help get you going.
It looks to me like this parts of this problem can are analogous to some of the other problems that we have solutions for.
One example is the Traveling Salesperson Problem, which looks at a person traveling between multiple cities.
This community posts has some example of users implementing the TSP:
https://support.dwavesys.com/hc/en-us/community/posts/360028972434
Another useful example is the Nurse Scheduling Problem.
We have a code example in our examples repo that might be helpful:
https://github.com/dwave-examples/nurse-scheduling
You might want to take a look at the examples page as well:
https://cloud.dwavesys.com/leap/examples
A third example would be the Knapsack example, which is also in the examples repo:
https://github.com/dwave-examples/knapsack
Yet another example is the Map Colouring Problem:
The above examples all have elements of the problem you are trying to formulate on the QPU.
Another approach is to formulate your problem as a QUBO if that's possible, which can be converted and solved on the QPU as an Ising Hamiltonian.
For larger problems, the LeapHybridSampler can be used:
https://docs.ocean.dwavesys.com/projects/system/en/stable/reference/generated/dwave.system.samplers.LeapHybridSampler.sample_qubo.html
Yet another way to solve this problem is by creating a set of small penalty models and bringing them together to form a larger penalty model, representing your problem.
Using a similar method as discussed in these posts:
The tricky bit will be in formulating the problem.
I would suggest taking a look at the above examples to determine how to formulate a simple part of the problem you'd like to solve, and then post your progress so the community can help guide you forward.
It's a little easier to help on the individual steps, rather than in deciding a direction in which to go to solve a problem.
I hope this was helpful.
Please do follow up with more questions!
Please sign in to leave a comment.