I am trying to figure out a way to create routes for trucks to complete a list of orders(drops/stops), while minimizing distance traveled.

  • There is only ever 1 company warehouse in the area.
  • The trucks have to deliver based on capacity.
  • Each truck can hold a maximum (usually 18 pallets).
  • Each order will be for a number underneath that maximum.
  • There will be a maximum number of trucks specified.
  • When trucks are finished with their route, they will return to the company warehouse.

I already have all of the orders, the pallets they are requesting, and the distance between each point.

I am an absolute simpleton when it comes to complex problems like these... I am hoping that someone has a simple (relatively) solution, or an article of some sort that could help me down my path.

  • $\begingroup$ underneath $\: \mapsto \:$ "which is at most" $\;\;\;$ ? $\;\;\;\;\;\;\;$ $\endgroup$
    – user12859
    Jul 22 '14 at 20:21
  • $\begingroup$ The maximum number of trucks only matters if there is some unmentioned constraint (perhaps a relevant time limit), since otherwise the truck with the highest maximum could just do all of the trips, returning to the warehouse between trips. $\;$ $\endgroup$
    – user12859
    Jul 22 '14 at 20:22
  • 1
    $\begingroup$ I don't think I really understand the details of your problem specification, but you might look at integer linear programming: I suspect your problem could be specified as an integer linear program and then solved with an off-the-shelf ILP solver. Spend some time doing some Googling and searching on this site and reading in textbooks to learn about ILP and how to use it, then see if it lets you do what you want. $\endgroup$
    – D.W.
    Jul 22 '14 at 21:52
  • 2
    $\begingroup$ Have you heard of the Traveling Salesman problem? $\endgroup$
    – Raphael
    Jul 22 '14 at 22:13
  • 2
    $\begingroup$ FYI Unhappy Truckers and Other Algorithmic Problems $\endgroup$
    – Guy Coder
    Jul 22 '14 at 23:33

A metaheuristic would do. I would opt for a Large Neighbourhood Search (LNS), a Genetic Algorithm (GA), or Tabu Search (TS).

  • $\begingroup$ This is rather vague. Can you give more detail? Why would those techniques work? Would any one of them be better than the others? $\endgroup$ Sep 18 '14 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.