9
$\begingroup$

I was given the task to model the following problem and find a solution for it, but as I do not have any experience in this field, I already have trouble classifying it.

There are a number of vehicles and a (possibly much greater) number of transportation-tasks that should be assigned to the vehicles.
One task consists of fetching a good from one station and bringing it to another station, while there are multiple stations, each of which can act as both a start- or an endpoint.
There are different kinds of transportation tasks and not every vehicle can do every kind of task.
Also, the arcs/edges between the stations have a capacity of 1, meaning that one vehicle occupies it for a specific amount of time.
At the stations, there also is a waiting time, meaning that maybe a queue of waiting vehicles arises (let's assume the queue can have infinite length).
One vehicle can only do one task at a time, but can put succeeding tasks in a queue.
And, last but not least, new tasks are being generated continuously, so the algorithm has to work "on-line".

The objective is to minimize the time it takes to complete all tasks.

From what I have read so far, this could be a job shop scheduling problem with sequence-dependent setup time, as there are multiple "machines" (the stations doing the on- and offloading "job") and what is actually the task in real life (the transportation of the goods), could be modeled as a setup time for the job, which is dependent from the preceding task, because the end-position of the preceding task determines the time the vehicle needs to get to the new start-position.

  1. Is that correct?
  2. How do I model such a system to find a good enough solution?
  3. For the future, are there ways how I can differentiate between different problem-classes? I have the feeling that Linear Optimization, Assignment, Scheduling, Network Flows, Routing, etc. are quite similar and with some adjustments could all somehow fit the problem...
$\endgroup$
  • 3
    $\begingroup$ Welcome to OR.SE! To me your problem seems to have some similarities with the vehicle routing problem with pickups and dropoffs (VRPPD) or the closely related dial-a-ride problem. Those problems lack some of the features of yours (e.g., the queuing aspect) but maybe their literature will still help you. $\endgroup$ – LarrySnyder610 Feb 14 at 14:49
  • $\begingroup$ I don't quite understand your question #3. Are you asking in the context of this particular problem, or in general? If general, perhaps it makes more sense to post this as a separate question (although it's pretty broad and might be hard for folks to provide good answers). $\endgroup$ – LarrySnyder610 Feb 14 at 14:49
  • $\begingroup$ Thank you! I think you are right, the VRPPD is quite similar. There are some examples on how to implement such a problem with Google OR-Tools, but how would I add the constraint that only one vehicle can be using an arc at a time? $\endgroup$ – DocRobson Feb 14 at 15:12
  • $\begingroup$ I am not familiar with the OR-Tools examples, so I can't comment on how to add that constraint. You could post a new question that gives the details of the OR-Tools example and asks specifically how to formulate the constraint. Also include your own attempt(s) at doing so and why they failed. $\endgroup$ – LarrySnyder610 Feb 14 at 17:52
  • 1
    $\begingroup$ Your problem shares some elements with the problem of unloading container ships in a port. The port problem involves moving cranes and either trucks or rail cars into position, occupying berths (similar to occupying links in your case), and possibly limits on which vehicles (and possibly which cranes) are suitable for which cargoes. I vaguely recall seeing an example of constraint programming being applied to that problem (but I can't recall where I saw it). $\endgroup$ – prubin Feb 14 at 20:39
3
$\begingroup$

Richer vehicle routing problems don't usually fall into a 'neat' academic classification and you're unlikely to find an exact classification for this one. Roughly speaking, your problem is a dynamic (a.k.a. realtime) pickup-delivery vehicle routing problem, with additional restrictions on vehicle-job assignment and a capacity limit on vehicles of one job on-board. So far, this is reasonably standard and has been covered in a few different papers. The constraint 'the arcs/edges between the stations have a capacity of 1...' is the particularly strange one though (probably related to container loading / docks?), and this puts the problem beyond any standard classification. I'm 99% certain no papers will have covered a model exactly like this.

My advice would be to look at algorithms that solve the dynamic pickup delivery vehicle routing problem and see if any of these could be adapted to handle your 'arc capacity' constraint. Usually algorithms which solve these using a combination of heuristics and metaheuristics are more successful than exact methods (i.e. mixed integer programming) as exact methods don't tend to scale that well for vehicle routing problems. If your problem size is really small an exact method might work though.

| improve this answer | |
$\endgroup$

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.