Reputation: 131
My problem is a modification of the Capacitated Vehicle Routing Problem (CVRP) that will eventually include time windows as well.
Since time windows are already built into the examples, it shouldn't be too hard for me to figure them out. However, I need to change one of the core constraints of the CVRP examples, and I'm a bit lost on how to do it.
In the system I'm trying to model, a Vehicle
can leave its Depot
, go to several different Customers
, and load up on material. However, where my model differs from the examples is that the Vehicle
can visit any Depot
mid-chain to deposit its current load.
I've been going over the documentation trying to figure out how to do this, and my basic understanding so far is that I'd have to change the definition of Depot
(maybe by implementing Standstill
) to be able to be part of the chain of places the vehicle visits, and/or maybe just integrate Depot
into Customer
with some kind of special rule that a visit to a Depot
empties the vehicle instead of increasing the demand.
I've also been looking at shadow variables and variable listeners, but I don't know if that's the right way to go. It's all a little confusing.
Can anyone offer some tips or advice, or point me in the right direction as to where to start before I dig myself too far into a hole?
Upvotes: 3
Views: 427
Reputation: 1846
Based on Geoffrey's suggestion, rename your Vehicle
class to VehicleTrip
and let it point to the previous and the next trip by giving it a value previousVehicleTrip
and nextVehicleTrip
, and give it a variable start time and end time (code examples in Kotlin):
class VehicleTrip(
...,
var startTime: LocalDateTime? = null,
var endTime: LocalDateTime? = null,
val previousVehicleTrip?: VehicleTrip = null,
val nextVehicleTrip?: VehicleTrip = null
) : Standstill {
...
}
You can set these values when initiating your VehicleTrips
. When you get a StackOverFlowError
based on the VehicleTrip.hashCode()
, simply override the hashCode()
function of the VehicleTrip
class. (Maybe someone has a better suggestion for dealing with this?)
In your Customer
class, you should have a variable arrivalTime
(like in the CVRPTW example) which is a custom shadow variable. In the listener class of this variable you usually only update the arrival time of a vehicle at a customer, and the arrival times of the customers that come next in this trip. Now, you also need to update all the times of the trips that come after the trip your current customer is in.
For example, you might have two trips VT1
and VT2
, and three customers C1
, C2
, and C3
. When changing from
VT1 - C1 - VT2 - C2 - C3
to
VT1 - C2 - C1 - VT2 - C3
the things you want updated are (in order)
C2.arrivalTime
C1.arrivalTime
VT1.endTime
VT2.startTime
C3.arrivalTime
VT2.endTime
Notice that in the TimeWindowedCustomer
example, the variable listener only does steps 1. and 2., so we have to add steps 3. until 6.
To do this, start by adding @CustomShadowVariable
annotations to the start and end times of VehicleTrip
(and don't forget to mark VehicleTrip
as a planning entity), which uses the same variable listener class as the time windowed customer:
class VehicleTrip(
...,
@CustomShadowVariable(
variableListenerRef = PlanningVariableReference(
entityClass = TimeWindowedCustomer::class,
variableName = "arrivalTime"
))
var startTime: LocalDateTime? = null,
...
) : Standstill {
...
}
Now in the ArrivalTimeUpdatingVariableListener
class, you can add steps 3. until 6. similar to how steps 1. and 2. are implemented. Make sure that you keep the order of updating these variables, and that you notify the ScoreDirector
when changing a variable with the beforeVariableChanged()
and afterVariableChanged()
methods.
Upvotes: 1