Keeping with my pattern of posts based on OR Tools GitHub issues, (issue #968) asked how to model having multiple alternatives for pickup locations and dropoff locations.
Alternative nodes
My motivation for solving this problem is that I had been thinking about a similar case for a while. Specifically, in the case of ambulances picking up patients for transport to an emergency room, I had been rolling over some ideas for how to model the delivery node. In the real world, it is easy to just say “take the patient to the nearest emergency room.” However, when setting up the solver, you have to pair the pickup with the delivery. Previously I had a routine to match up patients with nearest emergency rooms, but it seems somewhat redundant—I’m solving the same problem the solver is solving. Furthermore, although “nearest neighbor” has a pretty strict definition, it could be the case that multiple emergency rooms are approximately the same distance from the patient, and so picking one over the others prior to running the model might eliminate a better global solution that serves more customers. Rather than pairing up one patient with one emergency room, another approach is to pair one patient with multiple nearby emergency rooms.
The question expanded this problem to include multiple alternate pickup locations. While that doesn’t make sense in the patient-emergency room example, it does make sense for other applications. It is also interesting because of the need to pair a pickup and a delivery when both ends of the pair can be one of multiple nodes. In short, it is a slightly more interesting problem to solve.
Generating random alternative pickups and deliveries
In my python OR-tools setup, I have code that generates customer events by generating a random location and a random time window. I also have code that can duplicate an event’s details and then shift the new event into a different slot in time—modeling situations like repeated demands, say once a week or once a month.
This case is similar to the repeated shifted events, except I want to
hold time constant and shift the location. So to model multiple
alternative events that are perfect substitutes for each other, I just
tweaked my code a bit to generate a duplicate event with the same
time window but a new random location. Then I created a hash
map—alternatives—to track the substitute locations, along with
an originals hash map that tracks what the original events are
based on an event’s (duplicate or original) index.
# picks is pickup events
# deliv is delivery events
# both need to have alternatives generated
for (p,d) in zip(picks,deliv):
# print(p.index,d.index)
pd_pairs[p.index] = [p.index,d.index]
dp_pairs[d.index] = [p,d]
alternatives[p.index] = [p.index]
alternatives[d.index] = [d.index]
originals[p.index] = p
originals[d.index] = d
# generate alternates if needed
# in this case, same number of alternates for pickup, delivery
for _n in range(num_alternates):
# copy pickup
(lat,lon) = S.generate_stops(1)
copy_pickup = ev.Event(lat,lon,
p.event_type,
p.tw_open,
p.tw_close,
p.service_time)
# calling events.add_events populates the event index
events.add_event(copy_pickup)
# save index in alternatives list under original event key
alternatives[p.index].append(copy_pickup.index)
# save a link to original event based on this copy's index as key
originals[copy_pickup.index]=p
# copy delivery
(lat,lon) = S.generate_stops(1)
copy_deliv = ev.Event(lat,lon,
d.event_type,
d.tw_open,
d.tw_close,
d.service_time)
# again, calling events.add_events populates the event index
events.add_event(copy_deliv)
# save index in alternatives list under original event key
alternatives[d.index].append(copy_deliv.index)
# save a link to original event based on this copy's index as key
originals[copy_deliv.index]=d
# for output routine hacking
dp_pairs[copy_deliv.index]=[p,d]
In words, the outer loop loads up each pickup and delivery pair. The
inner loop creates num_alternates alternatives for each pickup and
delivery (to keep things simple, there are the same number of
alternatives for both pickup and delivery). By linking the original
pickup index to the pickup alternatives, and the original dropoff
index to the dropoff alternatives, I can achieve the many-to-many
combinations without having to build a crazy data structure.
Pickup and delivery constraints
The next wrinkle is setting up the constraints that make sure the pickups and deliveries are matched up properly. To do this I loop over all the “events” (pickup, dropoff, depot and “overnight” returns to depot) and apply the appropriate constraints.
Pickup and dropoff times
First up is setting the time window boundaries. For everything other than dropoffs, the minimum and maximum times are set by the event. For the dropoff events, I refer back to the original pickup event to set the minimum event time, but ignore the maximum time for now, as follows:
for e in events.events:
if (e.tw_open is not None and
e.event_type != "dropoff"
):
# pickups (and other) restricted to happen inside time window
time_dimension.CumulVar(routing.NodeToIndex(e.index)).SetRange(
int(e.tw_open.total_seconds()), int(e.tw_close.total_seconds()))
if e.event_type == "dropoff":
# deliver *after* pickup
orig_deliv = originals[e.index]
pickup_event = dp_pairs[orig_deliv.index][0]
pickup_time = pickup_event.tw_open.total_seconds()
# set delivery time bounds using "original" pickup time, and
# skip the max time (will be set with other constraint)
time_dimension.CumulVar(routing.NodeToIndex(e.index)).SetMin(
int(pickup_time))
Serving one pickup, one delivery out of alternatives
The pickup and delivery constraints are set as follows. The loop is over each pickup and delivery pair from the original set.
for pair in pd_pairs.values():
The pair is an two-element array that holds the pickup index at slot
0, and the delivery index at slot 1. These are used to grab all the
alternative pickups and deliveries, which are in turn used to set a
“perform just one” type of disjunction.
all_pickups = [ routing.NodeToIndex(pi) for pi in alternatives[pair[0]] ]
# only serve one of the alternative pickups
pickup_disjunction_index = routing.AddDisjunction(all_pickups, penalty)
all_deliver = [ routing.NodeToIndex(di) for di in alternatives[pair[1]] ]
# only serve one of the alternative delivery nodes
deliver_disjunction_index = routing.AddDisjunction(all_deliver, penalty)
I wondered about the need for delivery alternatives disjunction. On the one hand, I kept it in because I had it in the regular case. But I was curious if it was needed. Only the one pickup node can serve the alternative destination nodes, so only one will get served, which means just one of the alternative destination nodes will get paired up. Adding the delivery nodes disjunction would apply a penalty to not serving any of the destinations nodes, but effectively that penalty is already incurred if one of the pickup nodes is dropped. So to figure it out, I ran a bunch of test runs with and without adding the disjunction using just a handful of demands (so that the model would converge faster), and found that the solutions had roughly the same quality with and without the delivery node disjunctions. In fact, the only difference I found was that with the delivery disjunction, the solver converged in about 12 seconds on average, while without the delivery disjunction, the solver took the full two minutes to converge. So the delivery disjunction may not change the answer, but it certainly helps the solver figure out that answer faster.
Same vehicle requirement
The next requirement is to make sure the pickup node and the delivery node are both served by the same vehicle. The preceding constraints just make sure that just one pickup and one delivery out of the set are served, but so far there is no requirement that the same vehicle makes both the pickup and the delivery!
Setting up this constraint is a little bit tricky because I don’t know
in advance which pickup and which delivery node is served. As the
solver runs, it should pick just one of each (given the above
disjunction constraint). The unserved alternative nodes will have a
VehicleVar value of -1, while the single chosen “served” node among
the alternates has a positive VehicleVar. To make sure that the
pickup and delivery vehicles are the same, I take the maximum of all
the possible vehicles for both the pickup alternatives and delivery
alternatives, and require that these two maximum values be equal to
each other.
pickup_vehicles = [ routing.VehicleVar(i) for i in all_pickups ]
deliver_vehicles = [ routing.VehicleVar(i) for i in all_deliver ]
# same vehicle requirement across alternatives
solver.AddConstraint(solver.Max(pickup_vehicles) == solver.Max(deliver_vehicles))
So if there are three alternates for pickup and delivery, the constraint statement is saying:
max(-1, -1, 3) == max(-1, 3, -1)
The constraint will force that the single non-negative value in the pickup vehicle array and the delivery vehicle array will be identical, thus ensuring the same vehicle performs the pickup and delivery.
Pickup before delivery
In a similar vein, it is necessary to make sure that the delivery time
is after the pickup time. Once again, faced with a multiple of
possible nodes, I had to use an aggregate function like solver.Max
to pick the “active” node’s value. However, it seems that the
cumulative values for an unserved node are not automatically zero or
negative if that node isn’t being served. In tests, I discovered a
few cases in which an unserved node had a positive value for time. My
guess is that during the iterations, the node was at one point picked
as the best alternative out of the disjunction set, but then a later
iteration picked a different node, and further that the solver does
not go back and reset the cumulative values to zero of nodes that drop
out of the solution set.
To handle this, it is necessary to multiply the time dimension value
by the active state of the node (zero or one). This zeros
out the time value at inactive nodes, thus letting the solver.Max
trick work properly.
pickup_active = [ routing.ActiveVar(i) for i in all_pickups ]
deliver_active = [ routing.ActiveVar(i) for i in all_deliver ]
pickup_times = [ time_dimension.CumulVar(i) for i in all_pickups ]
deliver_times = [ time_dimension.CumulVar(i) for i in all_deliver ]
# multiply node time by the active state, to zero out inactive nodes
pickup_cross_active = [p*v for (p, v) in zip(pickup_times,pickup_active)]
deliver_cross_active = [p*v for (p, v) in zip(deliver_times,deliver_active)]
# deliver *after* pickup
solver.AddConstraint(
solver.Max(pickup_cross_active) <= solver.Max(deliver_cross_active))
Limiting in-vehicle time
The next thing I needed to do was to make sure that the travel time from pickup to delivery did not exceed one hour more than the straight-line travel time. Note that the solver will generate the cheapest total travel cost. It doesn’t care about anything else. So for example I’ve seen solutions where an item is picked up on day one and carried around for days until the optimal dropoff time occurs. If you don’t tell the solver in some way that some solutions are ridiculous, it will happily dive down a rabbit hole in search of optimal solutions that make no sense in practice.
I like to treat the in-vehicle time as a kind of step function. Up to some point, it is no big deal, but then very quickly it shifts from acceptable to unbearable. If the item being transported is a person, people will allow some variance for travel time and for picking up other passengers, but at a certain point, the “extra” delay is unacceptable. Similarly, if the items are packages or documents, the sender will accept some delay, but then at some point will lose patience. Overnight shippers promise overnight delivery. Customers don’t care if the package arrives early in the day or late in the day, but they’ll be pretty upset if the package arrives on the second day.
Depending on the business case, this tipping point might be a fixed value, or it might be a fraction of the expected trip time. A package might be allowed a few hours of travel time across a city, while a person might only accept a travel time that is two times longer than a straight trip. Whatever the business rules might be, the constraint has to apply to every origin and destination pair. This makes it interesting given that in this case there are multiple potential origins and destinations for each pair, and each pairing has a different travel time. The solution can be handled using something like the following double loop, which applies a constant value as the travel limit.
# only allow max of 1 hour over travel time from A to B
for o in all_pickups:
o_node = routing.IndexToNode(o)
# the time at the pickup node, iff it is active
pickup_cross_active_time = routing.ActiveVar(o) * time_dimension.CumulVar(o)
for d in all_deliver:
d_node = routing.IndexToNode(d)
travel_time = lookup_fn[o_node][d_node] + travel_limit
# The time at the delivery node iff it is active AND the
# pickup node is active
deliver_cross_active_time = routing.ActiveVar(o) * routing.ActiveVar(d) * time_dimension.CumulVar(d)
solver.AddConstraint(
deliver_cross_active_time <= pickup_cross_active_time + travel_time)
This routine loops over every combination of possible origin and possible destination in this pickup and delivery pairing set. The outer loop creates a variable for the candidate pickup alternative pickup time by multiplying the time by the active state of the node. This variable is zero if the node is not active, or the pickup time if it is.
The inner loop cycles over the candidate delivery nodes. For
each candidate pair, first the code fetches the travel time from the pickup to
the delivery. The constraint I’m setting here is that the in-vehicle
time cannot be more than one hour above this baseline time. In a real
application this limit would obviously be more interesting than that,
reflecting real world conditions and requirements. So in this case the
lookup_fn (really a two dimensional list) returns the travel time,
and the travel_limit holds the pre-set limit. In practice this
would probably also be a function taking both origin and destination
nodes.
The next line generates the delivery time variable. This variable is
zero if either the candidate origin node or the candidate
destination node is zero. The reason this double multiply is needed
is obvious when you consider the constraint set up in the following
line. Each of these constraints will always be active and binding.
In the case that both nodes are inactive, the deliver time is zero,
the pickup time is zero, and the travel time is positive. The
constraint can be obeyed even though it is non-binding to the solution,
because 0 < 0 + travel_limit is always true. If both the origin alternative o and the
delivery alternative d
are active, then the constraint is binding, forcing the positive
delivery time to be less than the pickup time plus the maximum travel
time allowed. If the pickup node o is active and the delivery node is
not, then the deliver_cross_active_time should be zero, which will always be less
than the pickup time, so no problem.
The only really tricky case is when the delivery node d is active but
the pickup node o is not. In that case, the pickup time is zero, but
the delivery time is not. If I didn’t multiply the delivery time
value by the origin active state, then I would get a very
difficult-to-satisfy constraint of delivery_time < 0 + travel_limit. But by multiplying the delivery time value by both
active node states, the constraint is back to 0 < 0 + travel_limit,
which again is easily satisfied.
In this way I’m using the boolean active variables to enforce a flavor
of conditional constraints, but ones that are active for every
combination of potential pickup and potential delivery pairs. That’s
a lot of constraints. I wasn’t sure whether it was better in terms of
solution time to have lots of constraints that “degenerated” to 0 < N, or whether it was better to set up conditional constraints. So I
set up a test case, and it turned out that using conditional
constraints resulted in slower solver times in general (I ran 30 tests
of each, and saw about a 25% runtime difference). So at least in this
case, this poor-man’s conditional constraint is the best approach.
First in, first out
The last thing needed is to require first in, first out (FIFO) conditions. Once again this isn’t strictly necessary in the general case, but might be required in a specific application. Imagine a shared ride service, in which passengers who get on first typically expect that they will get dropped off first. Similarly, loading large bulky items like couches or refrigerators might require a last in, first out loading regime. This doesn’t result in an optimal delivery schedule, and wouldn’t be necessary for pickup and delivery of, say, documents. But it is sometimes necessary, and handling it in the case of multiple alternatives was interesting.
I have an earlier post that addresses applying FIFO constraints to the pickups and deliveries. Visit that post for the gory details. The only point worth mentioning is that I had to create a dedicated FIFO dimension that monotonically increases by 1. Using the existing time dimension will not work. The multiple alternatives make setting up the FIFO constraint a little bit trickier than normal, but it yields to the same “active node” trick used above.
Unlike the previous loops, this routine loops over all combinations
pickup and delivery pairs, not just over alternatives for a single
original pair. The outer loop (pair a) uses the ActiveVar() function to
get the active pickup and delivery nodes’ FIFO dimension values, as
well as the active pickup and delivery times. The inner loop does the
same for the b pair, with the caveat that the a pair is different
than the b pair.
for pair in dp_pairs.values():
# note that dp_pairs holds complete objects, not just indices
# original pickup object
pickup_a = pair[0]
# original delivery object
deliv_a = pair[1]
# need to access the index field of object in the following
all_pickups_a = [ routing.NodeToIndex(pi) for pi in alternatives[pickup_a.index] ]
all_deliveries_a = [ routing.NodeToIndex(pi) for pi in alternatives[deliv_a.index] ]
pickup_vehicle_a = [ routing.VehicleVar(i) for i in all_pickups_a ]
pickup_fifo_active_a = [ routing.ActiveVar(i) * fifo_dimension.CumulVar(i) for i in all_pickups_a ]
deliver_fifo_active_a = [ routing.ActiveVar(i) * fifo_dimension.CumulVar(i) for i in all_deliveries_a ]
pickup_a_early = pickup_a.tw_open.total_seconds() # same for all alternatives
travel_time_a = lookup_fn[pickup_a.index][deliv_a.index] + travel_limit
drop_a_late = pickup_a.tw_close.total_seconds() + travel_time_a
for pair_b in dp_pairs.values():
pickup_b = pair_b[0]
deliv_b = pair_b[1]
if pickup_b == pickup_a :
# same pair, don't constrain
continue
pickup_b_early = pickup_b.tw_open.total_seconds()
pickup_b_late = pickup_b.tw_close.total_seconds()
pickup_b_index = routing.NodeToIndex(pickup_b.index)
deliv_b_index = routing.NodeToIndex(deliv_b.index)
The reason I compute the active nodes’ early pickup time, late delivery time, and
travel time is that I don’t want to bother setting a FIFO type
constraint on nodes that cannot possibly be on the same vehicle at the
same time. This can be determined by examining the allowed time
windows for the a pair and the b pair. If the time windows don’t
overlap, then there is no need to apply the FIFO constraint.
#
# check if overlap in time. if not, don't bother with constraint
#
if (pickup_b_early > drop_a_late or pickup_a_early > pickup_b_late ):
continue
One final note with this if statement: the knowledge about the time windows is known before the solver starts, and so I can use that here to decide whether or not to set the constraint at all. In what comes next, I’m using a conditional constraint, but there the condition is not known until the solver gets rolling. The conditions in a conditional constraint are dependent upon the candidate solution being evaluated by the solver. Of course I could insert the time windows condition into that conditional constraint as well, but that would be silly. I already know the outcome even before the solver starts, so it is more efficient to use it outside of the solver run.
If the code makes it past the if statement then the b pickup and
delivery pair overlaps the a pair and the FIFO constraint might be
needed. Whether or not the FIFO constraint is relevant to a and b
pairs is dependent upon the current solution proposed by the
model—whether they pairs are served by the same vehicle, and whether
a has been picked up before b.
The condition is built in two parts. First the vehicle_condition
variable is 1 (true) if and only if the vehicle used for the a
pickup and delivery is the same as that used for the b pickup and
delivery. Second, the early_condition variable is 1 (true) if and
only if the pickup of a has occurred before the pickup of b. The
variable combined_conditions is 1 (true) only if both these
conditions are true.
all_pickups_b = [ routing.NodeToIndex(pi) for pi in alternatives[pickup_b.index] ]
all_deliveries_b = [ routing.NodeToIndex(pi) for pi in alternatives[deliv_b.index] ]
pickup_vehicle_b = [ routing.VehicleVar(i) for i in all_pickups_b ]
pickup_fifo_active_b = [ routing.ActiveVar(i) * fifo_dimension.CumulVar(i) for i in all_pickups_b ]
deliver_fifo_active_b = [ routing.ActiveVar(i) * fifo_dimension.CumulVar(i) for i in all_deliveries_b ]
# conditional: same vehicle A and B
vehicle_condition = solver.Max(pickup_vehicle_a) == solver.Max(pickup_vehicle_b)
# conditional: if pickup A before pickup B
early_condition = solver.Max(pickup_fifo_active_a) <= solver.Max(pickup_fifo_active_b)
combined_conditions = vehicle_condition * early_condition
# constraint: require delivery of A before delivery of B
fifo_constraint = solver.Max(deliver_fifo_active_a) <= solver.Max(deliver_fifo_active_b)
expression = solver.ConditionalExpression(
combined_conditions,
fifo_constraint,
1)
# print("conditional constraint",early_condition,fifo_constraint)
solver.AddConstraint(
expression >= 1
)
As with the in-vehicle trip time constraint, I had an option to choose
whether to use a conditional constraint here, or whether to fake it by
setting up a regular constraint that devolved into 0 <= 0 in cases
in which the condition does not apply. I set up a test, and for some
reason in this case the conditional constraint results in the faster
execution time for the solver, this time with about a 10 percent
difference. So I stuck with the conditional constraint.
Solver results
I’ve run the code hundreds of times to test out various things, and given that it is just random pairs of pickups and deliveries with a faked up travel time between the two, the actual results are very uninteresting. However, just to prove that the solutions really do respect all the constraints set above, I’ve copied some output below.
This output is taken from the following case. The problem extends over one week, with two vehicles starting at two different depots, each with a capacity of 5 items. There are 50 original pairs of pickup and delivery items, with each given 3 alternative locations, for a total of 200 pairs of pickups and deliveries, or 400 nodes for the solver to consider. I expect before the model even starts that 300 of these nodes (150 pickups, 150 deliveries) will be dropped, as they are redundant.
In terms of the timing of the problem, I set the starting time for the pickups as early as 8:00 AM Monday morning, and set the ending time horizon to be Friday at 6:00 PM. At the end of each work day, there is a requirement that each vehicle return to the depot until 8:00 AM the following morning. The pickups and deliveries are randomly generated on a uniform plane, with the time windows of the delivery shifted to be one hour after the opening and closing times of the pickup. The time windows can be as long as the full 5 days of the work week, but recall that there is a constraint that forces the dropoff to happen at most 1 hour (plus travel time) after the item’s corresponding pickup. Further, as the vehicles are parked at the depot each night, pickups and deliveries can only happen from 8:00 AM to 6:00 PM each day.
Given the largish size of the problem, the solver took about 15 minutes to get to the point where all of the pickup and delivery pairs had an active alternative, and then kept churning to improve the solution for the full 30 minutes I allowed the solver to run. By dumping the solver log to the screen, and because I know the disjunction penalty is 10,000, it is pretty easy to spot when all of the demands are satisfied: the intermediate solver value dropped about 20,000 (how much dropping one pickup and one delivery would cost the solution1) in one step:
...
I0117 10:34:49.579301 192 search.cc:244] Solution #94 (21486, objective maximum = 1000002, time = 860442 ms, branches = 1123320, failures = 606573, depth = 33, neighbors = 117737, filtered neighbors = 23968, accepted neighbors = 94, memory used = 186.64 MB, limit = 47%)
I0117 10:35:55.266170 192 search.cc:244] Solution #95 (1560, objective maximum = 1000002, time = 926129 ms, branches = 1504682, failures = 797346, depth = 33, neighbors = 117751, filtered neighbors = 23982, accepted neighbors = 95, memory used = 186.67 MB, limit = 51%)
...
The program dumps each vehicle’s route information line by line for each node visited. Most of the work is performed by the first vehicle (Route 0) with only some tasks performed by the second vehicle (Route 1). Each route starts at the depot, and then visits nodes for pickups and deliveries. A pickup line looks like this:
-> 176:: [12, 172, 174, 176] Load(0) Fifo(2) Time(2 days, 8:11:21, 2 days, 9:06:03)
The 176 is the node visited, and the array [12, 172, 174, 176]
shows all of the possible alternate nodes. The Load(0) means the
vehicle had nothing on board as it arrived at the node for the pickup,
and the Fifo(2) indicates that this is the third node visited (the
first being the depot, and the second being the depot again at the end
of Monday as no trips were scheduled for Monday). Finally the time
entry shows the minimum and maximum time scheduled for the pickup activity.
A delivery entry looks like this:
-> 173:: [12, 172, 174, 176] -- [62, 173, 175, 177] Load(2) Fifo(4) Time(2 days, 8:31:16, 2 days, 9:25:58)
Again, the first number on the row indicates the node being visited,
in this case 173. The first array [12, 172, 174, 176] shows which
pickup set is being served, and the second array [62, 173, 175, 177]
gives the delivery alternatives (including the visited node 173).
The Load(2) entry means the vehicle has two items on board as it
enters node 173, and the Fifo(4) value means this is the fifth
node visited. You can verify that FIFO constraints are being obeyed
because the first pickup (node 176) is in the pickup array shown on
the row ([12, 172, 174, 176]), and all other earlier pickups have
already been dropped off, and no later pickups were dropped off earlier.
The full solution is shown below. By inspecting each row in each route, it can be seen that all of the constraints for the problem are being met.
The Objective Value is 632
Route 0:400:: --depot-- Load(0) Fifo(0) Time(0:00:00, 0:00:00)
-> 404:: --depot-- Load(0) Fifo(1) Time(1 day, 18:00:00, 1 day, 18:01:00)
-> 176:: [12, 172, 174, 176] Load(0) Fifo(2) Time(2 days, 8:11:21, 2 days, 9:06:03)
-> 202:: [17, 202, 204, 206] Load(1) Fifo(3) Time(2 days, 8:23:09, 2 days, 9:17:51)
-> 173:: [12, 172, 174, 176] -- [62, 173, 175, 177] Load(2) Fifo(4) Time(2 days, 8:31:16, 2 days, 9:25:58)
-> 10:: [10, 160, 162, 164] Load(1) Fifo(5) Time(2 days, 8:41:29, 2 days, 9:36:11)
-> 67:: [17, 202, 204, 206] -- [67, 203, 205, 207] Load(2) Fifo(6) Time(2 days, 8:50:31, 2 days, 9:45:13)
-> 165:: [10, 160, 162, 164] -- [60, 161, 163, 165] Load(1) Fifo(7) Time(2 days, 9:11:01, 2 days, 10:05:43)
-> 244:: [24, 244, 246, 248] Load(0) Fifo(8) Time(2 days, 9:20:29, 2 days, 10:15:11)
-> 324:: [37, 322, 324, 326] Load(1) Fifo(9) Time(2 days, 9:37:38, 2 days, 10:32:20)
-> 245:: [24, 244, 246, 248] -- [74, 245, 247, 249] Load(2) Fifo(10) Time(2 days, 9:44:21, 2 days, 10:39:03)
-> 327:: [37, 322, 324, 326] -- [87, 323, 325, 327] Load(1) Fifo(11) Time(2 days, 9:55:08, 2 days, 10:49:50)
-> 11:: [11, 166, 168, 170] Load(0) Fifo(12) Time(2 days, 10:00:36, 2 days, 10:55:18)
-> 61:: [11, 166, 168, 170] -- [61, 167, 169, 171] Load(1) Fifo(13) Time(2 days, 10:13:04, 2 days, 11:07:46)
-> 18:: [18, 208, 210, 212] Load(0) Fifo(14) Time(2 days, 10:28:40, 2 days, 11:23:22)
-> 146:: [7, 142, 144, 146] Load(1) Fifo(15) Time(2 days, 10:42:37, 2 days, 11:37:19)
-> 8:: [8, 148, 150, 152] Load(2) Fifo(16) Time(2 days, 10:53:35, 2 days, 11:48:17)
-> 213:: [18, 208, 210, 212] -- [68, 209, 211, 213] Load(3) Fifo(17) Time(2 days, 11:12:49, 2 days, 12:07:31)
-> 57:: [7, 142, 144, 146] -- [57, 143, 145, 147] Load(2) Fifo(18) Time(2 days, 11:24:27, 2 days, 12:19:09)
-> 0:: [0, 100, 102, 104] Load(1) Fifo(19) Time(2 days, 11:38:46, 2 days, 12:33:28)
-> 58:: [8, 148, 150, 152] -- [58, 149, 151, 153] Load(2) Fifo(20) Time(2 days, 11:48:31, 2 days, 12:43:13)
-> 50:: [0, 100, 102, 104] -- [50, 101, 103, 105] Load(1) Fifo(21) Time(2 days, 12:06:39, 2 days, 13:01:21)
-> 190:: [15, 190, 192, 194] Load(0) Fifo(22) Time(2 days, 12:26:13, 2 days, 13:20:55)
-> 310:: [35, 310, 312, 314] Load(1) Fifo(23) Time(2 days, 12:44:31, 2 days, 13:39:13)
-> 390:: [48, 388, 390, 392] Load(2) Fifo(24) Time(2 days, 12:55:06, 2 days, 13:49:48)
-> 65:: [15, 190, 192, 194] -- [65, 191, 193, 195] Load(3) Fifo(25) Time(2 days, 13:10:03, 2 days, 14:04:45)
-> 21:: [21, 226, 228, 230] Load(2) Fifo(26) Time(2 days, 13:21:27, 2 days, 14:16:09)
-> 313:: [35, 310, 312, 314] -- [85, 311, 313, 315] Load(3) Fifo(27) Time(2 days, 13:41:57, 2 days, 14:36:39)
-> 98:: [48, 388, 390, 392] -- [98, 389, 391, 393] Load(2) Fifo(28) Time(2 days, 13:50:26, 2 days, 14:45:08)
-> 218:: [19, 214, 216, 218] Load(1) Fifo(29) Time(2 days, 13:59:40, 2 days, 14:54:22)
-> 231:: [21, 226, 228, 230] -- [71, 227, 229, 231] Load(2) Fifo(30) Time(2 days, 14:27:03, 2 days, 15:21:45)
-> 126:: [4, 124, 126, 128] Load(1) Fifo(31) Time(2 days, 14:42:13, 2 days, 15:36:55)
-> 217:: [19, 214, 216, 218] -- [69, 215, 217, 219] Load(2) Fifo(32) Time(2 days, 15:01:22, 2 days, 15:56:04)
-> 127:: [4, 124, 126, 128] -- [54, 125, 127, 129] Load(1) Fifo(33) Time(2 days, 15:11:06, 2 days, 16:05:48)
-> 26:: [26, 256, 258, 260] Load(0) Fifo(34) Time(2 days, 15:17:12, 2 days, 16:11:54)
-> 261:: [26, 256, 258, 260] -- [76, 257, 259, 261] Load(1) Fifo(35) Time(2 days, 15:27:16, 2 days, 16:21:58)
-> 182:: [13, 178, 180, 182] Load(0) Fifo(36) Time(2 days, 15:43:51, 2 days, 16:38:33)
-> 63:: [13, 178, 180, 182] -- [63, 179, 181, 183] Load(1) Fifo(37) Time(2 days, 15:55:34, 2 days, 16:50:16)
-> 16:: [16, 196, 198, 200] Load(0) Fifo(38) Time(2 days, 16:09:25, 2 days, 17:04:07)
-> 154:: [9, 154, 156, 158] Load(1) Fifo(39) Time(2 days, 16:23:41, 2 days, 17:18:23)
-> 201:: [16, 196, 198, 200] -- [66, 197, 199, 201] Load(2) Fifo(40) Time(2 days, 16:39:48, 2 days, 17:34:30)
-> 159:: [9, 154, 156, 158] -- [59, 155, 157, 159] Load(1) Fifo(41) Time(2 days, 16:55:07, 2 days, 17:49:49)
-> 406:: --depot-- Load(0) Fifo(42) Time(2 days, 18:00:00, 2 days, 18:01:00)
-> 110:: [1, 106, 108, 110] Load(0) Fifo(43) Time(3 days, 8:19:07, 3 days, 14:57:24)
-> 109:: [1, 106, 108, 110] -- [51, 107, 109, 111] Load(1) Fifo(44) Time(3 days, 8:33:00, 3 days, 15:11:17)
-> 3:: [3, 118, 120, 122] Load(0) Fifo(45) Time(3 days, 14:34:04, 3 days, 15:25:59)
-> 6:: [6, 136, 138, 140] Load(1) Fifo(46) Time(3 days, 15:06:58, 3 days, 15:58:53)
-> 20:: [20, 220, 222, 224] Load(2) Fifo(47) Time(3 days, 15:30:22, 3 days, 16:20:39)
-> 119:: [3, 118, 120, 122] -- [53, 119, 121, 123] Load(3) Fifo(48) Time(3 days, 15:48:00, 3 days, 16:38:17)
-> 139:: [6, 136, 138, 140] -- [56, 137, 139, 141] Load(2) Fifo(49) Time(3 days, 15:54:12, 3 days, 16:44:29)
-> 5:: [5, 130, 132, 134] Load(1) Fifo(50) Time(3 days, 16:29:14, 3 days, 16:52:57)
-> 184:: [14, 184, 186, 188] Load(2) Fifo(51) Time(3 days, 16:51:09, 3 days, 17:14:52)
-> 70:: [20, 220, 222, 224] -- [70, 221, 223, 225] Load(3) Fifo(52) Time(3 days, 16:57:06, 3 days, 17:20:49)
-> 133:: [5, 130, 132, 134] -- [55, 131, 133, 135] Load(2) Fifo(53) Time(3 days, 17:08:19, 3 days, 17:32:02)
-> 189:: [14, 184, 186, 188] -- [64, 185, 187, 189] Load(1) Fifo(54) Time(3 days, 17:23:49, 3 days, 17:47:32)
-> 408:: --depot-- Load(0) Fifo(55) Time(3 days, 18:00:00, 3 days, 18:01:00)
-> 410:: --depot-- Load(0) Fifo(56) Time(4 days, 18:00:00, 4 days, 18:01:00)
-> 412:: --depot-- Load(0) Fifo(57) Time(5 days, 18:00:00, 5 days, 18:01:00)
-> 402:: --depot-- Load(0) Fifo(58) Time(6 days, 23:59:00, 7 days, 0:00:00)
-> EndRoute 0.
Route 1:401:: --depot-- Load(0) Fifo(0) Time(0:00:00, 0:00:00)
-> 405:: --depot-- Load(0) Fifo(1) Time(1 day, 18:00:00, 1 day, 18:01:00)
-> 320:: [36, 316, 318, 320] Load(0) Fifo(2) Time(2 days, 8:03:12, 2 days, 11:38:20)
-> 358:: [43, 358, 360, 362] Load(1) Fifo(3) Time(2 days, 8:11:42, 2 days, 11:46:50)
-> 40:: [40, 340, 342, 344] Load(2) Fifo(4) Time(2 days, 8:26:54, 2 days, 12:02:02)
-> 86:: [36, 316, 318, 320] -- [86, 317, 319, 321] Load(3) Fifo(5) Time(2 days, 8:37:01, 2 days, 12:12:09)
-> 93:: [43, 358, 360, 362] -- [93, 359, 361, 363] Load(2) Fifo(6) Time(2 days, 8:57:01, 2 days, 12:32:09)
-> 345:: [40, 340, 342, 344] -- [90, 341, 343, 345] Load(1) Fifo(7) Time(2 days, 9:08:19, 2 days, 12:43:27)
-> 242:: [23, 238, 240, 242] Load(0) Fifo(8) Time(2 days, 9:24:03, 2 days, 12:59:11)
-> 241:: [23, 238, 240, 242] -- [73, 239, 241, 243] Load(1) Fifo(9) Time(2 days, 9:34:46, 2 days, 13:09:54)
-> 44:: [44, 364, 366, 368] Load(0) Fifo(10) Time(2 days, 9:46:33, 2 days, 13:21:41)
-> 367:: [44, 364, 366, 368] -- [94, 365, 367, 369] Load(1) Fifo(11) Time(2 days, 9:55:17, 2 days, 13:30:25)
-> 332:: [38, 328, 330, 332] Load(0) Fifo(12) Time(2 days, 10:10:59, 2 days, 13:46:07)
-> 331:: [38, 328, 330, 332] -- [88, 329, 331, 333] Load(1) Fifo(13) Time(2 days, 10:28:05, 2 days, 14:03:13)
-> 270:: [28, 268, 270, 272] Load(0) Fifo(14) Time(2 days, 10:42:21, 2 days, 14:17:29)
-> 32:: [32, 292, 294, 296] Load(1) Fifo(15) Time(2 days, 10:51:26, 2 days, 14:26:34)
-> 264:: [27, 262, 264, 266] Load(2) Fifo(16) Time(2 days, 11:01:27, 2 days, 14:36:35)
-> 236:: [22, 232, 234, 236] Load(3) Fifo(17) Time(2 days, 11:10:16, 2 days, 14:45:24)
-> 252:: [25, 250, 252, 254] Load(4) Fifo(18) Time(2 days, 11:17:32, 2 days, 14:52:40)
-> 269:: [28, 268, 270, 272] -- [78, 269, 271, 273] Load(5) Fifo(19) Time(2 days, 11:37:20, 2 days, 15:12:28)
-> 293:: [32, 292, 294, 296] -- [82, 293, 295, 297] Load(4) Fifo(20) Time(2 days, 11:44:26, 2 days, 15:19:34)
-> 263:: [27, 262, 264, 266] -- [77, 263, 265, 267] Load(3) Fifo(21) Time(2 days, 12:07:16, 2 days, 15:42:24)
-> 235:: [22, 232, 234, 236] -- [72, 233, 235, 237] Load(2) Fifo(22) Time(2 days, 12:19:48, 2 days, 15:54:56)
-> 251:: [25, 250, 252, 254] -- [75, 251, 253, 255] Load(1) Fifo(23) Time(2 days, 12:32:05, 2 days, 16:07:13)
-> 114:: [2, 112, 114, 116] Load(0) Fifo(24) Time(2 days, 12:42:12, 2 days, 16:17:20)
-> 31:: [31, 286, 288, 290] Load(1) Fifo(25) Time(2 days, 12:50:25, 2 days, 16:25:33)
-> 113:: [2, 112, 114, 116] -- [52, 113, 115, 117] Load(2) Fifo(26) Time(2 days, 13:11:41, 2 days, 16:46:49)
-> 280:: [30, 280, 282, 284] Load(1) Fifo(27) Time(2 days, 13:18:01, 2 days, 16:53:09)
-> 291:: [31, 286, 288, 290] -- [81, 287, 289, 291] Load(2) Fifo(28) Time(2 days, 13:32:05, 2 days, 17:07:13)
-> 80:: [30, 280, 282, 284] -- [80, 281, 283, 285] Load(1) Fifo(29) Time(2 days, 13:42:27, 2 days, 17:17:35)
-> 302:: [33, 298, 300, 302] Load(0) Fifo(30) Time(2 days, 14:02:11, 2 days, 17:37:19)
-> 299:: [33, 298, 300, 302] -- [83, 299, 301, 303] Load(1) Fifo(31) Time(2 days, 14:09:42, 2 days, 17:44:50)
-> 407:: --depot-- Load(0) Fifo(32) Time(2 days, 18:00:00, 2 days, 18:01:00)
-> 372:: [45, 370, 372, 374] Load(0) Fifo(33) Time(3 days, 8:09:36, 3 days, 10:12:59)
-> 278:: [29, 274, 276, 278] Load(1) Fifo(34) Time(3 days, 8:21:22, 3 days, 10:24:45)
-> 371:: [45, 370, 372, 374] -- [95, 371, 373, 375] Load(2) Fifo(35) Time(3 days, 8:34:35, 3 days, 10:37:58)
-> 376:: [46, 376, 378, 380] Load(1) Fifo(36) Time(3 days, 8:44:03, 3 days, 10:47:26)
-> 277:: [29, 274, 276, 278] -- [79, 275, 277, 279] Load(2) Fifo(37) Time(3 days, 8:55:59, 3 days, 10:59:22)
-> 377:: [46, 376, 378, 380] -- [96, 377, 379, 381] Load(1) Fifo(38) Time(3 days, 9:18:14, 3 days, 11:21:37)
-> 356:: [42, 352, 354, 356] Load(0) Fifo(39) Time(3 days, 9:27:23, 3 days, 11:30:46)
-> 47:: [47, 382, 384, 386] Load(1) Fifo(40) Time(3 days, 9:44:52, 3 days, 12:27:04)
-> 49:: [49, 394, 396, 398] Load(2) Fifo(41) Time(3 days, 9:55:52, 3 days, 12:38:04)
-> 357:: [42, 352, 354, 356] -- [92, 353, 355, 357] Load(3) Fifo(42) Time(3 days, 10:16:34, 3 days, 12:58:46)
-> 308:: [34, 304, 306, 308] Load(2) Fifo(43) Time(3 days, 10:29:33, 3 days, 13:12:28)
-> 385:: [47, 382, 384, 386] -- [97, 383, 385, 387] Load(3) Fifo(44) Time(3 days, 10:38:31, 3 days, 13:21:26)
-> 336:: [39, 334, 336, 338] Load(2) Fifo(45) Time(3 days, 10:47:23, 3 days, 13:30:18)
-> 399:: [49, 394, 396, 398] -- [99, 395, 397, 399] Load(3) Fifo(46) Time(3 days, 11:17:33, 3 days, 14:00:28)
-> 309:: [34, 304, 306, 308] -- [84, 305, 307, 309] Load(2) Fifo(47) Time(3 days, 11:38:38, 3 days, 14:23:19)
-> 348:: [41, 346, 348, 350] Load(1) Fifo(48) Time(3 days, 11:54:53, 3 days, 14:39:34)
-> 337:: [39, 334, 336, 338] -- [89, 335, 337, 339] Load(2) Fifo(49) Time(3 days, 12:17:03, 3 days, 15:01:44)
-> 349:: [41, 346, 348, 350] -- [91, 347, 349, 351] Load(1) Fifo(50) Time(3 days, 12:24:37, 3 days, 16:03:22)
-> 409:: --depot-- Load(0) Fifo(51) Time(3 days, 18:00:00, 3 days, 18:01:00)
-> 411:: --depot-- Load(0) Fifo(52) Time(4 days, 18:00:00, 4 days, 18:01:00)
-> 413:: --depot-- Load(0) Fifo(53) Time(5 days, 18:00:00, 5 days, 18:01:00)
-> 403:: --depot-- Load(0) Fifo(54) Time(6 days, 23:59:00, 7 days, 0:00:00)
-> EndRoute 1.
dropped 300 nodes
dropped nodes all satisfied by alternative nodes
-
The actual drop is just 19,926 which is less than 20,000. This is because adding those two extra nodes to the solution (saving 10,000 each) will also increase the total travel cost. ↩︎