我使用ortools pywrapcp来解决一个使用SUMO的微观流量模拟的部署问题。在解决了初始问题后，我将解决方案放入模拟并启动它。过了一段时间，由于额外的请求或某些参数（如时间矩阵）的变化，原来的问题发生了变化，我需要再次解决这个问题。这会一直重复下去，直到我的模拟场景结束。在某些情况下，求解器会卡在其中一个迭代中。忽略or-tools中的超时。一个运行场景的同事得到了相同的行为，另一个得到了解决方案。
我不知道这是一个bug还是我的系统设置导致了问题。我使用的是Windows 10和or-tools 9.7版。
由于很难重现这种行为，我提取了一个更大场景的状态，并删除了一些约束。运行此命令，我将得到以下日志：
## 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%)在此之后，CPU仍在工作，但没有产生新的输出，计算似乎卡住了。要解决的问题并不难，因为类似的问题已经在几分之一秒内解决了数百次。
如果我去掉初始解，就会得到一个完整的解，但这会减慢其他解的计算速度，这就是我引入它的原因。
为了测试我的示例，从第一个代码片段开始，这将创建数据模型，并使用名为ortools_pdp.py的第二个代码片段来生成和解决问题。原始文件可以在这里找到ortools_pdp.py。
我看到这些问题/讨论的关系：
- “当使用GUIDED_EXPLORE_EXPLORE达到time_limit时，解算器不会停止”：issue #2660、discussion #2993
- “在使用多阶段决策构建器时不考虑”：issue #2723、discussion #2994
似乎有两个问题：
1.为什么不遵守时限（或者如果定义错误：如何正确定义它？
1.为什么求解器不能像所有其他迭代一样快地找到一个好的解决方案（或者不给出初始解决方案）？
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
1条答案
按热度按时间mf98qq941#
你可以看看这个页面：https://developers.google.com/optimization/routing/routing_tasks
看看如何设置时间限制。