In a distribution center, a conveyor is moving shipping boxes where workers should pick up the box depending on the final destination of each box.
There are 156000 boxes to be sorted.
Each box needs 3~4 seconds to be sorted.
14 hours of work are available.
In order minimize the worker's number, it's possible to assign one worker to many destinations and even more than one worker if needed.
The table shows the destination and the boxes to be sent there.
What's it the best method to assign the workers to the destination? Any algorithm to be used?
Hi Murthada,
Your question is related to the so-called Traveling Salesman Problem (TSP) and its variants. It's typically a combinatorial optimization problem.
Here are some references of interest as guidelines to solve it:
- Application in logistic transport, follow http://www.wseas.us/e-library/transactions/economics/2011/54-095.pdf and https://hal.inria.fr/file/index/docid/144276/filename/garaix_ejorV2.pdf (several cost attributes may be included)
- Solving based on fast marching methods, follow https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1783106/pdf/zpq1118.pdf
- Solving based on graph methods, follow http://booksc.org/dl/8601274/84a6c9
- TSP with Matlab programming, follow http://www.ijaamm.com/uploads/2/1/4/8/21481830/v2n3p27.pdf
Hoping it will be helpfull
Two additional information in order to address more precisely your problem:
- The multiple traveling salesman problem (mTSP) as a generalization of the well-known traveling salesman problem (TSP): http://s3.amazonaws.com/academia.edu.documents/44104099/The_multiple_traveling_salesman_problem.pdf?AWSAccessKeyId=AKIAIWOWYYGZ2Y53UL3A&Expires=1496505230&Signature=ZdtuD2GsYIuLTnwItC1bOnTzhdA%3D&response-content-disposition=inline%3B%20filename%3DThe_multiple_traveling_salesman_problem.pdf
- TSP with time window: https://www.researchgate.net/profile/Sebastian_Urrutia3/publication/220090403_A_General_VNS_heuristic_for_the_traveling_salesman_problem_with_time_windows/links/56f00b7808ae52f8ad7f8bb0.pdf and http://ac.els-cdn.com/S2212567115009260/1-s2.0-S2212567115009260-main.pdf?_tid=02750548-486e-11e7-817d-00000aacb35d&acdnat=1496502478_a6cc3f08389ac998d2a17cb0f5e3ce9f
Regards
Article A General VNS heuristic for the traveling salesman problem w...
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms