11
$\begingroup$

I am researching a Vehicle Routing Problem for a safety insurance company that provides roadside assistance.

The company does not have a depot, as in classical VRP, and has a set of heterogeneous vehicles, as of their use (motorbike used for the easy cases, and tow trucks used for the hard ones). They don't have capacity limitations, but they have other constraints and limitations, such as road accessibility (not all vehicles can have access in all roads), type accessibility (you cannot send a motorbike to tow a car) and time limitations (a customer shouldn't be served - waiting more than T).

I am searching the literature for almost a week now, trying to approach it by searching for dynamic VRPs with no depots or multiple depot VRP (having the vehicles as depots), but I can't find a similar problem. Does anyone happen to know any work done on the subject?

Thank you very much.

EDIT : As I can see, and imagined, there is no current approach to roadside assistance routing problems. The answer by Oguz Toragay seems very interesting, but it needs much work. I have thought many variants that could fit, but don't. The problem I am facing is how to calculate a good objective function, as the problem is bi-objective (time and kilometers). I mean it's difficult, as I cannot solve this problem by exact methods, to have a metric that can evaluate a solution in comparison to another. Thank you very much once again!

Improve this question
$\endgroup$
2
  • $\begingroup$ What if you establish a dummy depot and set all the distances to/from the depot = 0, then solve it more like a classical VRP? Would that work at all? $\endgroup$
    – LarrySnyder610
    Commented Aug 29, 2019 at 17:11
  • $\begingroup$ You could take a look at skill based vrp's, where each vehicle can only visit a subset of customers. $\endgroup$
    – Albert Schrotenboer
    Commented Sep 3, 2019 at 17:09

5 Answers 5

Reset to default
10
$\begingroup$

This recent review on rich routing problems may be helpful:

http://repository.psau.edu.sa/jspui/retrieve/6358c84c-e14d-4e4c-8645-c8f7320606ab/EJOR_2015.pdf

A quick scan on the categories would suggest you have:

1.3.2 Multiple Depots

2.1.1.2 Heterogeneous Vehicles

2.2.1 Restrictions on Customer Waiting Time

2.2.2 Restrictions on Road Access

2.4 Compatibility Constraints

You will certainly not find a paper in the references which has the combination of all these special cases but looking into multiple ones should help you come up with your very own rich VRP - paper coming up?

Improve this answer
$\endgroup$
6
$\begingroup$

Stating the obvious, even if you don't have a depot in its traditional definition, you can still use dummy nodes as your depot(s). I think an area closer to what you are looking for can be Ambulance dispatching.

  • It has a richer literature compared to other roadside assistance type VRP.
  • Moreover, during disasters, the roads can be blocked or very hard to access and there are active researches for Ambulance (or emergency vehicles) relocation, dispatching, and routing during disaster reliefs. Hope one of these keywords help.
Improve this answer
$\endgroup$
5
$\begingroup$

Would you see, Multiple Traveling Salesman Problem (mTSP). I think with add some limitation (as your constraints), it might be useful.

Improve this answer
$\endgroup$
5
$\begingroup$

From the first look, you have an heterogeneous multi-depot site-dependent vehicle routing problem with time windows. I think you can use our solver for the deterministic variant of your problem: https://vrpsolver.math.u-bordeaux.fr. Efficiency of the solver of course depends on the size of your instances. An exact approach may be useful for you to estimate the quality of heuristics you will use/create for your problem. You can contact me if you need help to model your problem for our solver.

Improve this answer
$\endgroup$
4
$\begingroup$

Maybe you need to look at assignment problems, in which some tasks(customer) should be assigned to some trucks, not all connections are available (road access, waiting time) and you need to minimize the traveling time of each vehicle or alternatively maximize the served customers as your objective function.

Edit: here is a good1 book about assignment problems which includes both various models and also different solution methods. Also, have a look at this website (assigning fastest pick-ups to **** drivers with linear programming).

1 Patriksson, Michael. The traffic assignment problem: models and methods. Courier Dover Publications, 2015.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thank you so much, do you have any good paper in mind? Although I do have all connections available, I can operate on a complete graph. From all vehicles to all incidents (clients). $\endgroup$
    – dimboukosis
    Commented Aug 29, 2019 at 7:46
  • 2
    $\begingroup$ If every vehicle could be used to serve a single customer, this would be a good approach, as the assignment costs could be calculated using shortest path computations. However, if a vehicle can serve multiple customers, it is not clear how to define the costs as the driving distance depends on the previously served customer. $\endgroup$
    – Rolf van Lieshout
    Commented Aug 29, 2019 at 10:03
  • $\begingroup$ @RolfvanLieshout fantastic insight. Unfortunately, I have the latter case. A vehicle can serve multiple customers. Maybe a good approach would be the non fixed destination multiple TSP with time windows. $\endgroup$
    – dimboukosis
    Commented Aug 29, 2019 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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