How to classify and model this problem?

Question

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

Answer 1

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.