TW.CLOSE or OPEN Issue

[lineheide]

Hi, I have tried to run your code for the vrptw and its is working perfectly for the arp, but I have an issue when timewondows are applied, The following line is causing the issue: "wait_times = [max(0, ctrs['TWs'][i][TW.OPEN]-D[0,i]) for i in range(0,N)]". Python gives me an error that "'int' object is not subscriptable", which I found out lies in the ctrs['TWs'][i][TW.OPEN] part of it.

Do you also have this issue or does it work with you?

Thank you so much on beforehand.

Regards Line

[lineheide]

Also I was thinking, what if you have timewindows, for the individual nodes, but also an overall time window? So you both have L and tws? Because right now it only runs L if not tws. So that tws are met within a given timecontraint L.

[lineheide]

Okay so I think I solved my forst issue, another thing you still have a TODO comment in your code? can you tell me more about what that part is about (what's missing) :) thank you so much

Regards Line

[lineheide]

Additionally I thought about the fact that to seems like if demand for a single node is greater than C, it will take it as one route, but it would actually need to be split into two routes :)

[yorak]

Hi Line, great to hear you were able to resolve some of the issues.

The 'int' object is not subscriptable suggested that your TWs was originally not an array of of 2-tuples. Did you load the constraints from a .vrp file or build the ctr datastucture youself? Currently VeRyPy script does no validation to check that the data structures are of correct format. The ctrs['TWs'] should be of format [[0,float('inf'), (120,240), (350,720) ... ]] with the tuple at index 0 being the depot. This is also the way you could set the time window for the entire route: set it to for the depot! Although thinking of it now, the opening timewindow for the depot is not currently enforced (it is a silly constraint in any case as for single depot problems the timewindows could be shifted by that amount).

Regarding the TODOs. Only the parallel savings in the vrptw_savings branch supprots timewindows. And also there it is not complete. If you carefully read the issue #4 the current implementation of the savings function is not complete as it is not at all TW sensitive! (i.e. feasibility does not mean that the solutions are good!):

yorak: Now, in the callback of vrptw_savings.py:placeholder_vrptw_savings_f(D, ctrs) you can write the calculation of the time window overlapping savings value part s_t! One could probably come up with a savings formula of ones own, but I'd propose referring to the literature. E.g., see Solomon (1987) and Van Landeghem (1988) that both seem relevant.

The placeholder for the VRPTW savings code is here.

Was the TODO you referred to related to implementation of the savings function? Feel free to implement a savings criteria with similar call signature as placeholder_vrptw_savings_f to adjust the order savings algorithm considers the merges thus having a great impact to the solution quality. I have not done too much VRPTW work, but my understanding is that writing a good savings criteria for VRPTW is tricky.

[yorak]

lineheide: Additionally I thought about the fact that to seems like if demand for a single node is greater than C, it will take it as one route, but it would actually need to be split into two routes :)

Unfortunately VeRyPy does not support this variant of VRP (that is VRP with split deliveries, for which sometimes the abbreviation of SDVRP is used). I'm not too knowledgeable on the heuristics that are used to tackle this problem, but perhaps you can tailor the code to add that support. In addition, with an impact to solution quality, you can split too large deliveries in a preprocessing step.

[yorak]

lineheide: Also I was thinking, what if you have timewindows, for the individual nodes, but also an overall time window? So you both have L and tws? Because right now it only runs L if not tws. So that tws are met within a given timecontraint L.

Are you referring to line 192 in the vrptw_savings branch? The TW constraints have been checked just before this branch. The condition in the L constraint check branch on TWs is there just to avoid updating merged_cost if it has already been updated in in the TWs constraint check (and in a way that takes the possible waiting time into account). I hope this clarifies this.

If you referred some other part of the code, could you post a permalink to the file and line, thanks.

[yorak]

Also, if you would like to have a short chat e.g. in Teams on the current state of VRPTW support in VeRyPy, do not hesitate to drop an invitation to my email (can be found form my github profile). ;)

[yorak]

Closed as answered question on incomplete feature (VRPTW support).