How to solve Vehicle Routing Problem with Time Windows? about alns HOT 4 CLOSED

Hi @carol007!

The VRP complicates things a bit; you could look at this project for inspiration on how to generalise to multiple vehicles (hint: you might want to add a routes list to your State object).

A node in my TSP example is a tuple of (label, (x, y)). I would add a time window tuple to this, like (label, (x, y), (start, end)), where start is the earliest moment a visit can be planned, and end the latest.

Then you could modify the greedy repair strategy as follows. Within the set of unvisited nodes, first find those nodes that can be visited within the node's time window from the current end of each existing route. Add the node that is nearest to the end of some route to that route. If no unvisited nodes can be visited on time, make a new route just for that node.

from alns.

@N-Wouda Thank you a lot! yes I have already changed the nodes with tuple of (label, (x, y), (start, end)). In fact, I randomly set a time window picked from the standard normal distribution for a car to service a certain customer. And I feel confused about the concept of the objective function in your code. In my VRPTW problems with no capacities factor, should i modify and take the objective function as a cost function that is simultaneously included with EuDistance cost of coordinates and the cost of arriving_time+service_time from A to B? And is there any way to write my own operator？I am a fresher with ALNS and VRPTW, Sorry for bothering you, and thank you!!

from alns.

@carol007 you wrote

In my VRPTW problems with no capacities factor, should i modify and take the objective function as a cost function that is simultaneously included with EuDistance cost of coordinates and the cost of arriving_time+service_time from A to B?

That depends on your problem. If you consider the time windows hard constraints, I would not add them to the objective. The problem then is just to find the shortest routing such that all places are visited within their time windows.

If, however, time windows are an aspirational goal rather than a hard constraint, you could penalise their violation in the objective function. That could look something like this in your objective function:

    parameter * sum_{i in vertices} (max(start_i - arrival_i, 0) + max(arrival_i - end_i, 0)),

where parameter is some penalty coefficient. This penalises early and late arrivals.

And is there any way to write my own operator？

Certainly! Operators are functions with the following signature: (State, np.RandomState) -> State. Destroy operators get a complete State that they should break in some way. That broken State is then passed to a repair operator that should repair the State into a feasible solution. The new feasible solution is then evaluated, and if accepted is passed to a destroy operator in the next iteration. And so on.

Any operator should thus do something with the passed-in state. Typically that something involves randomness. You can use the np.RandomState object to draw random variates. If initialised with a fixed seed, that ensures your experiments are fully reproducible.

After writing an operator, you can add it to your heuristic by calling add_<repair/destroy>_operator on the ALNS instance.

from alns.

@carol007 I'm closing this issue because I have not heard from you for some time. If you something new to discuss, feel free to let me know by opening a new issue. Have a great day!

from alns.