Updates:
I also posted this question to the or-tools-dicuss forum.
This happens in OR-Tools version 9.6 and 9.7. In version 9.5 the problem solves very quickly. Posted this to github.
Question:
I use ortools pywrapcp to solve disposition problems for a microscopic traffic simulation using SUMO. After solving the initial problem I put the solution into the simulation and start it. After a while the original problem changes due to additional requests or the change of some parameters (such as time matrix) and I need to solve the problem again. This iterates until my simulation scenario ends. In some scenarios the solver is stuck in one of these iterations. A time out in or-tools is ignored. One colleague running the scenario gets the same behaviour, another one gets a solution.
I don't know if that is a bug or my system settings are causing problems. I'm using Windows 10 and or-tools version 9.7.
As it is difficult to reproduce this behaviour I extracted the state of a larger scenario and removed some constraints. Running this I get the following log:
## Done
WARNING: All log messages before absl::InitializeLog() is called are written to STDERR
I0000 00:00:1697184924.982494 19592 search.cc:276] Start search (memory used = 35.39 MB)
I0000 00:00:1697184924.982802 19592 search.cc:276] Root node processed (time = 0 ms, constraints = 279, memory used = 35.60 MB)
I0000 00:00:1697184924.983037 19592 search.cc:276] Solution #0 (58026, time = 0 ms, branches = 0, failures = 0, depth = 0, memory used = 35.72 MB)
I0000 00:00:1697184924.983112 19592 search.cc:276] Finished search tree (time = 0 ms, branches = 0, failures = 1, memory used = 35.79 MB)
I0000 00:00:1697184924.983178 19592 search.cc:276] End search (time = 1 ms, branches = 0, failures = 1, memory used = 35.80 MB, speed = 0 branches/s)
I0000 00:00:1697184924.983356 19592 search.cc:276] Start search (memory used = 35.84 MB)
I0000 00:00:1697184924.983465 19592 search.cc:276] Root node processed (time = 0 ms, constraints = 279, memory used = 35.84 MB)
I0000 00:00:1697184924.983615 19592 search.cc:276] Solution #1 (58026, time = 0 ms, branches = 33, failures = 1, depth = 33, memory used = 35.84 MB, limit = 0%)
I0000 00:00:1697184924.995302 19592 search.cc:276] Solution #2 (56508, maximum = 58026, time = 11 ms, branches = 37, failures = 3, depth = 33, MakePairActive, neighbors = 7829, filtered neighbors = 1, accepted neighbors = 1, memory used = 36.05 MB, limit = 0%)
After this the CPU is still working but no new output is generated, the calculation seems to be stuck. The problem to solve is not that hard, as similar problems were already solved hundreds of times in a fraction of a second before.
If I remove the initial solution a complete solution is calculated, but this slows down all other solution calculations, that's the reason I introduced it.
To test my example start the first code snippet, this creates the data model and uses the second snippet named ortools_pdp.py to generate and solve the problem. The original file can be found here ortools_pdp.py.
I am seeing relations to these issues/discussions:
- "Solver does not stop when time_limit is reached using GUIDED_LOCAL_SEARCH": issue #2660, discussion #2993
- "Timeout not respected when using multiple-phase decision builder": issue #2723, discussion #2994
There seem to be two questions:
- Why the time limit is not respected (or if defined it wrong: How can I define it correctly)?
- Why does the solver is not able to find a good solution as fast as all the other iterations (or without giving the initial solution)?
import ortools_pdp
class Request:
def __init__(self, id, from_node, to_node, is_new, direct_route_cost, current_route_cost, vehicle_index, vehicle, reservationTime) -> None:
self.id = id
self.from_node = from_node
self.to_node = to_node
self.is_new = is_new
self.direct_route_cost = direct_route_cost
self.current_route_cost = current_route_cost
self.vehicle_index = vehicle_index
self.vehicle = vehicle
self.reservationTime = reservationTime
def create_data_model():
data = {}
data['depot'] = 0 # node_id of the depot
data['cost_matrix'] = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 3194, 2274, 3829, 2274, 7230, 6899, 3042, 7230, 2274, 2797, 3717, 6899, 1687, 970, 3294, 6899, 3161, 3340, 2269, 6899, 3108, 892, 3091, 2274, 1665, 2224, 7230, 3702, 1293, 1687, 1687, 1687, 1687, 1687, 1687, 1687, 1687], [0, 3448, 0, 1744, 3078, 1744, 8150, 7163, 3963, 8150, 1744, 4569, 2966, 7163, 3545, 2922, 1211, 7163, 1554, 2549, 1742, 7163, 1501, 3526, 1414, 1744, 3112, 3997, 8150, 4622, 3151, 3545, 3545, 3545, 3545, 3545, 3545, 3545, 3545], [0, 1744, 1326, 0, 2323, 33, 6787, 6374, 2599, 6787, 33, 2603, 2211, 6374, 1841, 1218, 1641, 6374, 940, 2190, 296, 6374, 1240, 1821, 1605, 33, 1471, 2030, 6787, 3259, 1446, 1841, 1841, 1841, 1841, 1841, 1841, 1841, 1841], [0, 4093, 2747, 2389, 0, 2389, 8428, 8323, 4241, 8428, 2389, 4848, 532, 8323, 4190, 3810, 2827, 8323, 2714, 3709, 2388, 8323, 2661, 4171, 1883, 2389, 3390, 4275, 8428, 4900, 3796, 4190, 4190, 4190, 4190, 4190, 4190, 4190, 4190], [0, 1744, 1326, 33, 2323, 33, 6787, 6374, 2599, 6787, 33, 2603, 2211, 6374, 1841, 1218, 1641, 6374, 940, 2190, 296, 6374, 1240, 1821, 1605, 33, 1471, 2030, 6787, 3259, 1446, 1841, 1841, 1841, 1841, 1841, 1841, 1841, 1841], [0, 7062, 7478, 6558, 8113, 6558, 0, 12848, 5179, 101, 6558, 5188, 8001, 12848, 7636, 6419, 7578, 12848, 7445, 8440, 6553, 12848, 7392, 7134, 7375, 6558, 5529, 5700, 101, 4052, 7241, 7636, 7636, 7636, 7636, 7636, 7636, 7636, 7636], [0, 7036, 6289, 6335, 8156, 6335, 13406, 0, 9040, 13406, 6335, 9091, 8044, 97, 6237, 7181, 7203, 97, 5747, 4754, 6492, 97, 6077, 7114, 7405, 6335, 7959, 8519, 13406, 9700, 6184, 6237, 6237, 6237, 6237, 6237, 6237, 6237, 6237], [0, 2948, 3365, 2445, 3999, 2445, 5282, 8734, 0, 5282, 2445, 1987, 3888, 8734, 3522, 2306, 3465, 8734, 3332, 4327, 2440, 8734, 3279, 3021, 3262, 2445, 1299, 1470, 5282, 1247, 3128, 3522, 3522, 3522, 3522, 3522, 3522, 3522, 3522], [0, 7062, 7478, 6558, 8113, 6558, 101, 12848, 5179, 101, 6558, 5188, 8001, 12848, 7636, 6419, 7578, 12848, 7445, 8440, 6553, 12848, 7392, 7134, 7375, 6558, 5529, 5700, 101, 4052, 7241, 7636, 7636, 7636, 7636, 7636, 7636, 7636, 7636], [0, 1744, 1326, 33, 2323, 33, 6787, 6374, 2599, 6787, 33, 2603, 2211, 6374, 1841, 1218, 1641, 6374, 940, 2190, 296, 6374, 1240, 1821, 1605, 33, 1471, 2030, 6787, 3259, 1446, 1841, 1841, 1841, 1841, 1841, 1841, 1841, 1841], [0, 2689, 3941, 3022, 4576, 3022, 5657, 8856, 1968, 5657, 3022, 0, 4464, 8856, 3644, 2046, 4042, 8856, 3909, 4903, 3017, 8856, 3855, 2657, 3838, 3022, 1380, 1259, 5657, 1400, 3250, 3644, 3644, 3644, 3644, 3644, 3644, 3644, 3644], [0, 4006, 2659, 2301, 435, 2301, 8341, 8235, 4153, 8341, 2301, 4760, 0, 8235, 4103, 3722, 2739, 8235, 2627, 3621, 2300, 8235, 2573, 4084, 1796, 2301, 3302, 4187, 8341, 4813, 3709, 4103, 4103, 4103, 4103, 4103, 4103, 4103, 4103], [0, 7036, 6289, 6335, 8156, 6335, 13406, 97, 9040, 13406, 6335, 9091, 8044, 97, 6237, 7181, 7203, 97, 5747, 4754, 6492, 97, 6077, 7114, 7405, 6335, 7959, 8519, 13406, 9700, 6184, 6237, 6237, 6237, 6237, 6237, 6237, 6237, 6237], [0, 2541, 2909, 3363, 4918, 3363, 8926, 5297, 4738, 8926, 3363, 4595, 4806, 5297, 0, 2685, 4383, 5297, 2367, 1947, 3359, 5297, 2697, 2618, 4180, 3363, 3463, 4023, 8926, 5398, 1689, 85, 85, 85, 85, 85, 85, 85, 85], [0, 1043, 2694, 1775, 3329, 1775, 6685, 7138, 2309, 6685, 1775, 2127, 3217, 7138, 1926, 0, 2795, 7138, 2662, 3578, 1770, 7138, 2608, 867, 2591, 1775, 995, 1555, 6685, 3157, 1532, 1926, 1926, 1926, 1926, 1926, 1926, 1926, 1926], [0, 3512, 1474, 1808, 2295, 1808, 7863, 7741, 3675, 7863, 1808, 4282, 2183, 7741, 3609, 3244, 0, 7741, 2133, 3128, 1806, 7741, 2080, 3590, 694, 1808, 2824, 3709, 7863, 4335, 3215, 3609, 3609, 3609, 3609, 3609, 3609, 3609, 3609], [0, 7036, 6289, 6335, 8156, 6335, 13406, 97, 9040, 13406, 6335, 9091, 8044, 97, 6237, 7181, 7203, 97, 5747, 4754, 6492, 97, 6077, 7114, 7405, 6335, 7959, 8519, 13406, 9700, 6184, 6237, 6237, 6237, 6237, 6237, 6237, 6237, 6237], [0, 2559, 878, 839, 2740, 839, 7486, 5694, 3299, 7486, 839, 3419, 2628, 5694, 2524, 2033, 1786, 5694, 0, 1510, 995, 5694, 667, 2637, 1989, 839, 2448, 2846, 7486, 3958, 2149, 2524, 2524, 2524, 2524, 2524, 2524, 2524, 2524], [0, 2973, 1804, 2177, 3671, 2177, 8743, 4902, 4556, 8743, 2177, 5162, 3559, 4902, 2497, 3118, 2718, 4902, 1589, 0, 2329, 4902, 1592, 3051, 2920, 2177, 3705, 4590, 8743, 5215, 2121, 2497, 2497, 2497, 2497, 2497, 2497, 2497, 2497], [0, 2175, 1470, 470, 2105, 470, 6550, 6715, 2362, 6550, 470, 2969, 1993, 6715, 2272, 1931, 1570, 6715, 1438, 2432, 0, 6715, 1384, 2253, 1367, 470, 1511, 2396, 6550, 3021, 1878, 2272, 2272, 2272, 2272, 2272, 2272, 2272, 2272], [0, 7036, 6289, 6335, 8156, 6335, 13406, 97, 9040, 13406, 6335, 9091, 8044, 97, 6237, 7181, 7203, 97, 5747, 4754, 6492, 97, 6077, 7114, 7405, 6335, 7959, 8519, 13406, 9700, 6184, 6237, 6237, 6237, 6237, 6237, 6237, 6237, 6237], [0, 2946, 558, 1241, 2582, 1241, 7654, 6176, 3467, 7654, 1241, 4074, 2470, 6176, 3006, 2420, 1624, 6176, 573, 1562, 1240, 6176, 0, 3024, 1831, 1241, 2616, 3501, 7654, 4126, 2631, 3006, 3006, 3006, 3006, 3006, 3006, 3006, 3006], [0, 968, 2637, 1717, 3272, 1717, 6673, 7064, 2485, 6673, 1717, 2065, 3160, 7064, 1851, 224, 2737, 7064, 2604, 3504, 1712, 7064, 2551, 0, 2534, 1717, 932, 1492, 6673, 3145, 1457, 1851, 1851, 1851, 1851, 1851, 1851, 1851, 1851], [0, 3496, 1765, 1792, 2279, 1792, 7847, 7725, 3659, 7847, 1792, 4266, 2167, 7725, 3593, 3228, 812, 7725, 2117, 3112, 1790, 7725, 2063, 3574, 0, 1792, 2808, 3693, 7847, 4319, 3199, 3593, 3593, 3593, 3593, 3593, 3593, 3593, 3593], [0, 1744, 1326, 33, 2323, 33, 6787, 6374, 2599, 6787, 33, 2603, 2211, 6374, 1841, 1218, 1641, 6374, 940, 2190, 296, 6374, 1240, 1821, 1605, 33, 1471, 2030, 6787, 3259, 1446, 1841, 1841, 1841, 1841, 1841, 1841, 1841, 1841], [0, 1701, 2793, 1873, 3428, 1873, 5825, 7868, 1502, 5825, 1873, 1514, 3316, 7868, 2656, 1058, 2893, 7868, 2760, 3755, 1868, 7868, 2707, 1669, 2690, 1873, 0, 941, 5825, 2297, 2262, 2656, 2656, 2656, 2656, 2656, 2656, 2656, 2656], [0, 2044, 3297, 2377, 3931, 2377, 5703, 8212, 1380, 5703, 2377, 1198, 3820, 8212, 2999, 1402, 3397, 8212, 3264, 4259, 2372, 8212, 3211, 2013, 3194, 2377, 735, 0, 5703, 2175, 2605, 2999, 2999, 2999, 2999, 2999, 2999, 2999, 2999], [0, 7062, 7478, 6558, 8113, 6558, 101, 12848, 5179, 101, 6558, 5188, 8001, 12848, 7636, 6419, 7578, 12848, 7445, 8440, 6553, 12848, 7392, 7134, 7375, 6558, 5529, 5700, 101, 4052, 7241, 7636, 7636, 7636, 7636, 7636, 7636, 7636, 7636], [0, 3641, 4057, 3137, 4692, 3137, 4299, 9427, 1323, 4299, 3137, 1272, 4580, 9427, 4215, 2998, 4157, 9427, 4024, 5019, 3132, 9427, 3971, 3713, 3954, 3137, 2108, 2279, 4299, 0, 3820, 4215, 4215, 4215, 4215, 4215, 4215, 4215, 4215], [0, 910, 2652, 1733, 3287, 1733, 7295, 6194, 3107, 7295, 1733, 2965, 3175, 6194, 982, 1054, 2753, 6194, 2620, 2634, 1728, 6194, 2566, 988, 2549, 1733, 1832, 2392, 7295, 3767, 0, 982, 982, 982, 982, 982, 982, 982, 982], [0, 2541, 2909, 3363, 4918, 3363, 8926, 5297, 4738, 8926, 3363, 4595, 4806, 5297, 85, 2685, 4383, 5297, 2367, 1947, 3359, 5297, 2697, 2618, 4180, 3363, 3463, 4023, 8926, 5398, 1689, 85, 85, 85, 85, 85, 85, 85, 85], [0, 2541, 2909, 3363, 4918, 3363, 8926, 5297, 4738, 8926, 3363, 4595, 4806, 5297, 85, 2685, 4383, 5297, 2367, 1947, 3359, 5297, 2697, 2618, 4180, 3363, 3463, 4023, 8926, 5398, 1689, 85, 85, 85, 85, 85, 85, 85, 85], [0, 2541, 2909, 3363, 4918, 3363, 8926, 5297, 4738, 8926, 3363, 4595, 4806, 5297, 85, 2685, 4383, 5297, 2367, 1947, 3359, 5297, 2697, 2618, 4180, 3363, 3463, 4023, 8926, 5398, 1689, 85, 85, 85, 85, 85, 85, 85, 85], [0, 2541, 2909, 3363, 4918, 3363, 8926, 5297, 4738, 8926, 3363, 4595, 4806, 5297, 85, 2685, 4383, 5297, 2367, 1947, 3359, 5297, 2697, 2618, 4180, 3363, 3463, 4023, 8926, 5398, 1689, 85, 85, 85, 85, 85, 85, 85, 85], [0, 2541, 2909, 3363, 4918, 3363, 8926, 5297, 4738, 8926, 3363, 4595, 4806, 5297, 85, 2685, 4383, 5297, 2367, 1947, 3359, 5297, 2697, 2618, 4180, 3363, 3463, 4023, 8926, 5398, 1689, 85, 85, 85, 85, 85, 85, 85, 85], [0, 2541, 2909, 3363, 4918, 3363, 8926, 5297, 4738, 8926, 3363, 4595, 4806, 5297, 85, 2685, 4383, 5297, 2367, 1947, 3359, 5297, 2697, 2618, 4180, 3363, 3463, 4023, 8926, 5398, 1689, 85, 85, 85, 85, 85, 85, 85, 85], [0, 2541, 2909, 3363, 4918, 3363, 8926, 5297, 4738, 8926, 3363, 4595, 4806, 5297, 85, 2685, 4383, 5297, 2367, 1947, 3359, 5297, 2697, 2618, 4180, 3363, 3463, 4023, 8926, 5398, 1689, 85, 85, 85, 85, 85, 85, 85, 85], [0, 2541, 2909, 3363, 4918, 3363, 8926, 5297, 4738, 8926, 3363, 4595, 4806, 5297, 85, 2685, 4383, 5297, 2367, 1947, 3359, 5297, 2697, 2618, 4180, 3363, 3463, 4023, 8926, 5398, 1689, 85, 85, 85, 85, 85, 85, 85, 85]]
dp_reservations = [Request('16', 1, 12, False, 3717, 0, 1, 'vx', 2105.0), Request('18', 2, 13, False, 7163, 0, 1, 'vx', 2153.0), Request('19', 3, 14, False, 1841, 0, 1, 'vx', 2155.0), Request('23', 4, 15, False, 3810, 0, 1, 'vx', 2324.0), Request('26', 5, 16, False, 1641, 0, 1, 'vx', 2606.0), Request('27', 6, 17, False, 12848, 0, 0, 'vx', 2705.0), Request('28', 7, 18, False, 5747, 0, 1, 'vx', 2800.0), Request('29', 8, 19, False, 4327, 0, 0, 'vx', 2900.0), Request('30', 9, 20, False, 6553, 0, 0, 'vx', 3003.0), Request('31', 10, 21, False, 6374, 0, 1, 'vx', 3123.0), Request('32', 11, 22, True, 3855, 0, -1, 'vx', 3246.0)]
for res in dp_reservations:
if res.vehicle_index == -1:
delattr(res, 'vehicle_index')
data['pickups_deliveries'] = dp_reservations
do_reservations = [Request('0', 1, 23, False, 7114, 10281.06488188736, 1, 'v1', 142.0), Request('7', 2, 24, False, 7405, 10281.06488188736, 1, 'v1', 419.0), Request('12', 1, 25, False, 2402, 652.2643102156289, 1, 'v1', 655.0), Request('17', 6, 26, False, 7959, 10281.064635940005, 1, 'v1', 2111.0), Request('22', 6, 27, False, 4498, 4296.314635347553, 1, 'v1', 2251.0), Request('24', 7, 28, False, 6787, 3533.8704600340025, 0, 'v0', 2325.0)]
data['dropoffs'] = do_reservations
data['num_vehicles'] = 10
data['starts'] = [29, 30, 31, 32, 33, 34, 35, 36, 37, 38]
data['ends'] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
data['max_time'] = 14400
initial_routes = {0: [['21', '30', '27', '24', '29', '30', '29', '27'], 20132, [27, 10, 7, 29, 9, 21, 20, 18]], 1: [['20', '12', '16', '0', '22', '17', '31', '26', '12', '18', '26', '7', '16', '23', '19', '23', '19', '31', '28', '18', '28'], 49523, [26, 1, 2, 23, 28, 25, 11, 6, 12, 3, 17, 24, 13, 5, 4, 16, 15, 22, 8, 14, 19]], 2: [[], [], []], 3: [[], [], []], 4: [[], [], []], 5: [[], [], []], 6: [[], [], []], 7: [[], [], []], 8: [[], [], []], 9: [[], [], []]}
# initial_routes = {}
data['initial_routes'] = initial_routes
return data
def main():
data = create_data_model()
time_limit = 10
verbose = False
solution_ortools = ortools_pdp.main(data, time_limit, verbose)
if solution_ortools is None:
print("solution is None")
else:
print("solution found")
if __name__ == "__main__":
main()
# @file ortools_pdp.py
import numpy as np
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def set_travel_cost(data, routing, manager, verbose):
# Create and register a transit callback.
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['cost_matrix'][from_node][to_node]
if verbose:
print(' Register distance callback.')
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
return transit_callback_index
def add_cost_constraint(data, routing, transit_callback_index, verbose):
# Add costs/distance constraint.
if verbose:
print(' Add distance constraints...')
matrix_costs = int(np.sum(data['cost_matrix']))
dimension_name = 'Costs'
routing.AddDimension(
transit_callback_index,
0, # no slack
matrix_costs, # TODO reasonable max costs/distance
True, # start cumul to zero
dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
return distance_dimension
def add_transportation_requests_constraint(data, routing, manager, solver, distance_dimension, verbose):
if verbose:
print(' Add pickup and delivery constraints...')
for request in data['pickups_deliveries']:
pickup_index = manager.NodeToIndex(request.from_node)
delivery_index = manager.NodeToIndex(request.to_node)
if verbose:
print('pickup/dropoff nodes: %s/%s' % (request.from_node, request.to_node))
routing.AddPickupAndDelivery(pickup_index, delivery_index) # helps the solver
# use same veh for pickup and dropoff
solver.Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))
solver.Add(
distance_dimension.CumulVar(pickup_index) <=
distance_dimension.CumulVar(delivery_index)) # define order: first pickup then dropoff
if hasattr(request, 'is_new') and request.is_new: # is that a new request?
# allows to reject the order but gives penalty
if verbose:
print('allow to reject new reservation %s' % (request.id))
routing.AddDisjunction([pickup_index, delivery_index], 10000, 2)
def add_dropoff_constraint(data, routing, manager, verbose):
if verbose:
print(' Add dropoff constraints...')
for res in data['dropoffs']:
if verbose:
print('reservation %s in veh %s(%s), droppoff node: %s' %
(res.id, res.vehicle, res.vehicle_index, res.to_node))
index = manager.NodeToIndex(res.to_node)
routing.SetAllowedVehiclesForIndex([res.vehicle_index], index)
def solve_from_initial_solution(routing, manager, search_parameters, data, verbose):
solution_requests = data['initial_routes']
# get inital solution
inital_solution = []
if solution_requests is not None:
for index_vehicle in solution_requests:
# use request ids ([0]) here and align with current status of the requests
request_order = solution_requests[index_vehicle][0].copy()
for request_id in set(solution_requests[index_vehicle][0]):
# 0: done
# 1: only drop-off left
# 2: pick-up and drop-off left
old_status = solution_requests[index_vehicle][0].count(request_id)
new_status = 0
if request_id in [req.id for req in data['pickups_deliveries']]:
new_status = 2
elif request_id in [req.id for req in data['dropoffs']]:
new_status = 1
if new_status == 0:
# remove complete request
request_order = [req for req in request_order if req != request_id]
if old_status == 2 and new_status == 1:
# remove first occurance of the request
request_order.remove(request_id)
# translate new requests order (ids) to nodes order
# (e.g. [0,1,2,1,2] -> [0.to_node, 1.from_node, 2.from_node, 1.to_node, 2.to_node])
request_id_set = set(request_order) # e.g. [0,1,2]
# first occurance from behind (will be "to_node")
reverserd_request_order = request_order.copy()
reverserd_request_order.reverse() # e.g. [2,1,2,1,0]
first_occurance_from_behind = [reverserd_request_order.index(id) for id in request_id_set] # e.g. [0,1,4]
all_requests = data['pickups_deliveries'].copy()
all_requests.extend(data['dropoffs'].copy())
nodes_order = []
for index, req_id in enumerate(reverserd_request_order):
req = [r for r in all_requests if r.id == req_id][0]
if index in first_occurance_from_behind:
nodes_order.insert(0, manager.NodeToIndex(req.to_node))
else:
nodes_order.insert(0, manager.NodeToIndex(req.from_node))
# nodes_order = solution_requests[index_vehicle][2] # [2] for nodes
inital_solution.append(nodes_order)
routing.CloseModelWithParameters(search_parameters)
if verbose:
print('Initial solution:')
for index_vehicle, index_list in enumerate(inital_solution):
print('veh %s: %s' % (index_vehicle, [manager.IndexToNode(index) for index in index_list]))
initial_solution = routing.ReadAssignmentFromRoutes(inital_solution, True)
solution = routing.SolveFromAssignmentWithParameters(initial_solution, search_parameters)
return solution
def set_first_solution_heuristic(time_limit_seconds, verbose):
if verbose:
print(' Set solution heuristic...')
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC
search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.AUTOMATIC
search_parameters.time_limit.seconds = time_limit_seconds
# search_parameters.lns_time_limit.seconds = 7
# search_parameters.solution_limit = 100
# Switch logging on for the search
search_parameters.log_search = True
return search_parameters
def main(data: dict, time_limit_seconds=10, verbose=False):
"""Entry point of the program."""
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data['cost_matrix']), data['num_vehicles'],
data['starts'], data['ends'])
# Create Routing Model.
routing_parameters = pywrapcp.DefaultRoutingModelParameters()
# routing_parameters.solver_parameters.trace_propagation = True
# routing_parameters.solver_parameters.trace_search = True
routing = pywrapcp.RoutingModel(manager, routing_parameters)
# get solver
solver = routing.solver()
# define transit_callback and set travel cost
transit_callback_index = set_travel_cost(data, routing, manager, verbose)
# Add costs/distance constraint.
distance_dimension = add_cost_constraint(data, routing, transit_callback_index, verbose)
# Define Transportation Requests.
add_transportation_requests_constraint(data, routing, manager, solver, distance_dimension, verbose)
# Force the vehicle to drop-off the reservations it already picked up
add_dropoff_constraint(data, routing, manager, verbose)
print('## Done')
# Setting first solution heuristic.
search_parameters = set_first_solution_heuristic(time_limit_seconds, verbose)
time_limit_in_ms = 1000
solver.TimeLimit(time_limit_in_ms)
# Solve the problem.
if verbose:
print('Start solving the problem.')
if data['initial_routes']:
solution = solve_from_initial_solution(routing, manager, search_parameters, data, verbose)
else:
solution = routing.SolveWithParameters(search_parameters)
return solution
The solver really hangs. Bug report can be found here: https://github.com/google/or-tools/issues/3975
If you don't want to downgrade to version 9.5 a workaround is to unable the parameter that is responsible for this behavior:
Thanks to Mizux who localized the problem and suggests the workaround.