Arbitrary Depot Locations

[aaronzberger]

Thanks for making this amazing package! I have one use case which I could use some advice on:

I would like to make the depot locations arbitrary. That is, I have a large number of services in high-density across an area, and want to maximize the number of services to perform. The "vehicles" are people walking, so for my problem, I assume that driving to and parking at any location takes no time, and would like to simply find the routes which maximize the number of services performed, regardless of the depot. However, in each list, the person should return to the starting location of that list (or, at least, the optimizer should be aware of this cost). You can imagine the person drives and parks at this location, walks around and performs services, and then returns to their car. For simplicity, assume all the possible depots are all the houses.

Currently, I've formulated the problem as follows:
Define an arbitrary location p* to be infinite travel time to all houses and 0 travel time to all possible depots. Define the time it takes to travel from p* to any possible depot as some large amount of time t*. All vehicles must start and end at p*. Each possible depot has one service with two jobs: one t* after the route start time and ending a second later, and one t* before the route end time and ending a second later (each job takes 0 seconds). The max route time is set to 2xt* + original max route time, to give enough time for a vehicle to go to exactly one possible depot, complete a route, and return to p*. Remember that once a vehicle gets assigned a service, it must complete all jobs in that service (so a vehicle couldn't start at one possible depot and end at another).

This formulation doesn't seem to work (I'm getting routes from the optimizer, but noticing weird behavior like jumps that are clearly not optimal at all). I've looked at the dispatch feature, but it doesn't seem like there's a way to force the vehicle to return to the dispatch location at the end of the route.

Any ideas? I'm very open to new formulations as well. Thanks!

[reinterpretcat]

Hi, thanks for feedback!

Interesting use case, not sure that I got it precisely. One of the features, I'm considering to add the next, might help: optional start location. My plan is to model it internally with zero cost to any other location which sounds similar to your approach. I'm thinking to model it for the user facing API with another variation of Location enumeration, something like location with fixed distance/duration (e.g. zero) to any other location. Such location can be used to model no cost for start location and some fixed cost for end location (from any other location)

[aaronzberger]

Sorry for the late response. This sounds like a good addition, but I think it doesn't quite fit my use case: for my problem, the start and end location should be the same (and the optimizer must account for the cost of traveling between the last service and the end location). Thus, of all potential starting locations, the optimizer should essentially choose one, and then solve a normal VRP with that one as the depot. The difficulty in formulating this problem is that the depot is not known until the optimizer is finished, so we can't directly model the cost to return to the depot.

Happy to provide more explanation or visualization if needed. If you happen to see why my formulation isn't working, or have any suggestions on how to make it work, we would really appreciate it!