Google OR-Tools TSP spanning multiple days with start/stop times

Asked 26/11, 2020 at 20:38 Answered 23/12, 2020 at 5:4

Solved python python-3.x traveling-salesman or-tools vehicle-routing

I am using Google OR-Tools to optimize the routing of a single vehicle over the span of a several day.

I am trying to:

Be able to specify the number of days over which to optimize routing.
Be able to specify the start location and end location for each day.
Be able to specify the start time and end time for each day.

I have a set of 40 locations. For each day I want to include in my range of days for optimization, I prepend the start and end location to the matrix. So if I want to optimize for one day, I would have a total of 42 locations in my matrix. If I want to optimize for two days, I would have a total of 44 locations in my matrix. And so on. The pattern would like like this:

1 Day:
Matrix = [[start day 1], [end day 1], [location], [location], ... ]

2 Days:
Matrix = [[start day 1], [end day 1], [start day 2], [end day 2], [location], [location], ... ]

3 Days:
Matrix = [[start day 1], [end day 1], [start day 2], [end day 2], [start day 3], [end day 3], [location], [location], ... ]

I want to allow locations to be dropped in order to achieve a feasible solution, as well as only allow locations to be visited during their specified time windows, both of which I believe I have successfully implemented.

My current implementation is available here, as well as on GitHub.

I warmly welcome any suggestions, guidance, or support. Thank you!

Source: (Seeded with data for a two-day solution)

from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

Matrix = [[0,1706.7,526.4,0,1497,1136.3,1445.8,1728.3,864.4,1362.3,1443.2,1410,805.1,1031.5,781.1,1003.1,364.6,482.6,279.8,768.6,461.4,752.5,972.6,771.7,698.3,901.6,1086.9,994.2,416.7,737.5,1171.7,881.6,1052.1,1164.3,868.7,409.7,498.6,685.7,1693.3,1875.3,302.7,1297.1,1663.4,1427.8],[1614.3,0,1382.2,1614.3,2192.7,1851.9,2686.5,2995.8,2216.9,1545.3,1599.2,1550.6,1796.5,1685.3,1597.7,1518.5,1779.9,2033.2,1891.8,2295.5,2009.6,2279.4,2054.5,2040.4,1235.2,1249.6,1290.2,2433.5,1943.6,1074.2,1128.2,1229.6,1192.7,823.3,1106.1,1440.2,1528.1,2100.8,2357.4,2757.6,1586.5,1676.3,1929.1,1681.3],[534.8,1446.5,0,534.8,1885.4,1473.2,1834.2,2011.5,1252.8,1549,1561.5,1622,1094.3,1131.5,895.5,1103.1,656.3,871,738.7,1051.8,765.9,1035.7,1160.9,960,798.3,1047.8,1205.2,1277.4,699.9,476.7,877.2,999.9,1264.1,891.6,534.2,196.5,356.2,874,1881.6,2063.6,342.8,1448.6,1851.7,1566.8],[0,1706.7,526.4,0,1497,1136.3,1445.8,1728.3,864.4,1362.3,1443.2,1410,805.1,1031.5,781.1,1003.1,364.6,482.6,279.8,768.6,461.4,752.5,972.6,771.7,698.3,901.6,1086.9,994.2,416.7,737.5,1171.7,881.6,1052.1,1164.3,868.7,409.7,498.6,685.7,1693.3,1875.3,302.7,1297.1,1663.4,1427.8],[1418.2,2192.4,1835.2,1418.2,0,557.7,608.1,2149,1325.3,1031.6,1615.8,1986.8,1123.8,961,1040,1085.5,1439.8,1204.8,1545.6,1530.2,1879.6,1769.1,2234.4,2150.1,1315.1,1094.9,1339.3,1874.4,1834.9,1623.6,2265.6,1275.3,1628.9,1677.3,1770.8,1718.5,1891.8,2052.1,2750.3,2966.2,1662.4,2682,2788.7,2832.4],[1096.3,1832,1437.4,1096.3,568.8,0,1062.6,1896.2,966.1,651.1,1255.4,1626.4,687,521.4,600.4,725.1,1052.8,882.9,1223.7,1209.4,1557.7,1448.3,1918,1829.3,954.7,734.5,978.9,1558,1513,1200,1863.6,914.9,1268.5,1316.9,1331.2,1396.6,1569.9,1731.3,2433.9,2649.8,1340.5,2360.1,2472.3,2510.5],[1379.1,2741.6,1796.1,1379.1,651.6,1106.9,0,1834.1,1198.5,1580.8,2140,2536,1144.1,1439.4,1262.4,1496.3,1400.7,1165.7,1495.8,1231.5,1599.7,1470.2,1919.5,1851.2,1682.6,1644.1,1888.5,1559.5,1729,1826.7,2442.7,1824.5,2178.1,2226.5,1957.9,1679.4,1852.7,1753.4,2435.4,2651.3,1623.3,2433,2473.8,2693.1],[1799.2,3111,2046.1,1799.2,2171.9,2026.5,1868,0,1242.3,2252.5,2836.7,3064,1667.2,1962.5,1785.5,2019.4,1922.9,1692.7,1687.3,1240.7,1524.3,1185.1,1224.4,1507.6,2205.7,2328.9,2545.2,895.3,1653.6,2349.8,2362.4,2407.3,2706.1,2776.6,2431.9,1925.8,1948.6,1639.8,1415.3,1631.2,1854.1,1757.2,1778.7,2017.3],[805.5,2218.4,1222.5,805.5,1296.7,925.9,1181.5,1136.6,0,1151.9,1736.1,2046.8,566.6,861.9,684.9,918.8,827.1,592.1,781,449.8,818,688.7,1158.4,1069.7,1105.1,1228.3,1444.6,798.4,947.3,1249.2,1869.1,1306.7,1688.9,1676,1380.4,1105.8,1242.3,971.7,1674.3,1890.2,1049.7,1651.3,1712.7,1911.4],[1265.8,1550.9,1515,1265.8,1025.9,685.1,1519.7,2065.7,1135.6,0,811.6,1195.2,809.5,522.1,695.6,621.5,1148,1052.4,1380.7,1378.9,1727.2,1617.8,2087.5,1998.8,878.6,658.4,559.3,1727.5,1682.5,1187.1,1829.1,639.4,837.3,1117.1,1384.6,1518.6,1691.9,1900.8,2603.4,2819.3,1462.5,2394.8,2641.8,2513],[1419.8,1573.3,1501.6,1419.8,1678.7,1342.9,2162.9,2723.5,1793.4,840.4,0,972.9,1426.5,1232.7,1183.3,1027.1,1409.9,1631.2,1556.1,2036.7,1839.6,2109.4,2234.6,2033.7,865.2,922.3,542.6,2351.1,1773.6,1213.4,1855.4,622.7,746.7,1139.5,1395.4,1540.2,1713.5,1947.7,2955.3,3137.3,1484.1,2421.1,2803.8,2539.3],[1434.8,1610.4,1634.2,1434.8,2103.8,1763,2597.6,3058.1,2128,1292.3,1016.9,0,1707.6,1596.4,1508.8,1429.6,1670.5,1853.7,1712.3,2140.5,1854.6,2124.4,2249.6,2048.7,1146.3,1160.7,1008,2366.1,1788.6,1323.9,1902.6,982.4,579.5,1176.6,1521.4,1555.2,1728.5,1962.7,2970.3,3152.3,1499.1,2468.3,2840.9,2586.5],[745.9,1760.2,1028.4,745.9,1104,685.5,1195.2,1544.9,614.8,819.7,1383.1,1588.6,0,378.9,226.7,460.6,679.1,427.3,873.3,858.1,1207.3,1097,1566.7,1478,646.9,770.1,986.4,1206.7,1162.6,791,1454.6,848.5,1230.7,1217.8,922.2,1046.2,1219.5,1380,2082.6,2298.5,990.1,2009.7,2121,2138.5],[933.5,1687.2,1052,933.5,912.5,494,1406.3,1784.3,854.2,495.6,1198.2,1481.6,328.9,0,215,309.1,667.4,659.1,900.1,1097.5,1289.3,1336.4,1777.9,1577,670.5,589.7,834.1,1446.1,1267.5,814.6,1478.2,770.1,1123.7,1172.1,945.8,1090.6,1263.9,1491,2322,2537.9,1034.5,2043.9,2360.4,2162.1],[729,1645.1,913.3,729,1034.6,616.1,1294.4,1644.1,714,715.2,1209.3,1473.5,293.6,274.4,0,286.8,462.9,447.9,695.6,957.3,1084.8,1196.2,1573.4,1372.5,531.8,596.3,812.6,1305.9,1063,675.9,1339.5,733.4,1115.6,1102.7,807.1,934.4,1107.7,1286.5,2181.8,2397.7,878.3,1897.9,2220.2,2023.4],[995.2,1489.7,1077,995.2,1008,667.2,1501.8,1901.4,971.3,591.3,994.8,1284.1,550.9,369.2,287.1,0,750,735,982.7,1214.6,1371.9,1453.5,1810,1609.1,479.2,392.2,598.1,1563.2,1349,839.6,1503.2,572.6,926.2,974.6,970.8,1115.6,1288.9,1523.1,2439.1,2655,1059.5,2068.9,2477.5,2187.1],[350.3,1818.6,639.3,350.3,1473.6,1055.1,1475.4,1824.1,894,1154.2,1439.7,1530.2,732.6,713.4,463,749.8,0,471.9,283.8,863.5,673,885.7,1161.6,960.7,676.5,939.6,1083.4,1127.4,651.2,849.4,1285.9,878.1,1172.3,1276.2,980.6,522.6,695.9,874.7,1882.3,2064.3,466.5,1486.1,1852.4,1636.5],[437.4,2042,854.4,437.4,1269.3,908.6,1218.1,1566.8,636.7,1134.6,1649.8,1745.3,433.7,696.7,440.5,727.3,459,0,564.8,880,898.8,1118.9,1376.7,1175.8,971.8,1036.8,1253.1,1228.6,854.1,1072.8,1501,1173.4,1387.4,1499.6,1204,737.7,911,1089.8,2097.4,2279.4,681.6,1701.2,2067.5,1851.6],[279.5,1914.6,746.3,279.5,1579.2,1218.5,1506.8,1619,804.6,1401,1593.4,1617.9,887.3,960.2,709.8,996.6,291.3,564.8,0,621,410.3,643.2,1112.5,911.6,830.2,1093.3,1237.1,884.9,367.4,945.4,1392.9,1031.8,1260,1372.2,1076.6,629.6,693.7,765.7,1833.2,2015.2,536.1,1410.3,1803.3,1528.5],[800.2,2348.7,1050.6,800.2,1567.8,1294.7,1285.3,1226.6,510.5,1520.7,2101.7,2068.5,935.4,1230.7,1053.7,1287.6,874.2,932.8,638.6,0,512.4,442.6,1064.1,823.6,1356.8,1560.1,1745.4,684.3,658.1,1378.9,1670,1540.1,1710.6,1793.8,1436.4,930.3,953.1,725.6,1719.6,1901.6,858.6,1405.2,1689.7,1665.3],[407.8,2014.3,716.2,407.8,1813.5,1472.5,1531,1409.4,756.2,1698.5,1767.3,1734.1,1141.3,1274,1023.6,1310.4,605.1,818.8,323.7,450,0,433.6,881.3,680.4,1022.4,1225.7,1411,675.3,210.4,1044.5,1335.6,1205.7,1376.2,1459.4,1102,595.9,618.7,526.2,1602,1784,524.2,1205.8,1572.1,1453.5],[855.1,2395.3,1102,855.1,1798.4,1525.3,1515.9,1173.4,741.1,1751.3,2153.1,2119.9,1166,1461.3,1284.3,1518.2,978.8,1191.5,743.2,477.1,580.2,0,701.1,460.6,1408.2,1611.5,1796.8,439.3,709.5,1430.3,1646.7,1591.5,1762,1845.2,1487.8,981.7,1004.5,548.2,1474.6,1656.6,910,1057.4,1444.7,1317.5],[902.1,2028.4,1133.3,902.1,2345.6,1984.9,2055.1,1189.6,1266.5,2169.2,2184.4,2151.2,1653.7,1772.7,1536.7,1744.3,1151.1,1331.2,1061.6,1047,850.5,702.5,0,407.3,1439.5,1642.8,1828.1,510.1,784.2,1461.6,1279.8,1622.8,1793.3,1876.5,1519.1,1013,1115.7,539.5,904,1086,956.9,636.9,874.1,897],[746.1,2102,977.3,746.1,2147.9,1828.9,1865.4,1456.3,1090.6,2013.2,2028.4,1995.2,1497.7,1616.7,1380.7,1588.3,995.1,1175.2,905.6,826.6,694.5,448.6,347,0,1283.5,1486.8,1672.1,792.2,628.2,1305.6,1353.4,1466.8,1637.3,1720.5,1363.1,857,934.6,301.2,1170.7,1352.7,800.9,764.1,1140.8,1024.2],[714,1295.8,795.8,714,1312.1,971.3,1721.5,2071.2,1141.1,885.7,898.2,1089.2,720.7,733.5,521.9,485.6,704.1,969.8,850.3,1384.4,1133.8,1403.6,1528.8,1327.9,0,369,541.9,1645.3,1067.8,558.4,1222,336.6,731.3,780.7,689.6,834.4,1007.7,1241.9,2249.5,2431.5,778.3,1787.7,2198.3,1905.9],[927.4,1285.1,1044.2,927.4,1067,726.2,1560.8,2152.6,1222.5,650.3,929.6,1079.5,812.8,559.6,549,392.8,952.5,996.9,1098.7,1465.8,1347.2,1617,1742.2,1541.3,402.3,0,573.3,1814.4,1281.2,716.3,1358.3,368,721.6,770,913.8,1047.8,1221.1,1455.3,2462.9,2644.9,991.7,1924,2334.6,2042.2],[1066.9,1288.4,1148.7,1066.9,1353.6,1012.8,1847.4,2393.4,1463.3,510.3,522.8,932.7,1073.6,866.8,816.7,660.5,1057,1264.6,1203.2,1706.6,1486.7,1756.5,1881.7,1680.8,512.3,569.4,0,1998.2,1420.7,860.5,1502.5,269.8,571.2,854.6,1042.5,1187.3,1360.6,1594.8,2602.4,2784.4,1131.2,2068.2,2478.8,2186.4],[1033.9,2497.8,1280.8,1033.9,1937.1,1628.8,1633.2,906.4,844.6,1854.8,2331.9,2298.7,1269.5,1564.8,1387.8,1621.7,1157.6,1295,922,655.9,759,419.8,553.1,800.8,1587,1790.3,1975.6,0,888.3,1609.1,1749.2,1770.3,1940.8,2024,1666.6,1160.5,1183.3,888.4,1207.6,1389.6,1088.8,1106.3,1177.7,1366.4],[434.2,1998.9,700.8,434.2,1859.6,1498.9,1676.6,1555,901.8,1724.9,1751.9,1718.7,1167.7,1300.4,1050,1311.8,631.5,845.2,350.1,595.3,261.3,579.2,855.8,654.9,1007,1210.3,1395.6,820.9,0,1029.1,1320.2,1190.3,1360.8,1444,1086.6,580.5,603.3,509,1576.5,1758.5,508.8,1180.3,1546.6,1438.1],[660.4,1093.1,449.6,660.4,1614.9,1241.5,1863.4,2213.1,1283,1198.2,1213.4,1273.2,862.6,899.8,663.8,871.4,877.7,1079.3,937.9,1362.9,1077,1346.8,1472,1271.1,566.6,671.8,857.1,1588.5,1011,0,841.6,651.8,915.3,538.2,276.4,507.6,681.4,1185.1,2192.7,2374.7,653.9,1407.3,1817.9,1525.5],[1074.3,1158.2,863.3,1074.3,2242.2,1861.6,2474.8,2235.8,1893.4,1797.9,1840.7,1803.2,1482.7,1519.9,1283.9,1491.5,1296.9,1511.6,1279.7,1623.1,1337.2,1590,1294.5,1280.4,1186.7,1299.1,1484.4,1673.5,1271.2,855.8,0,1279.1,1445.3,943.7,772.3,813.5,690.4,1340.8,1733.2,2031,828.6,894.3,1304.9,1012.5],[846.2,1208.6,928,846.2,1291.8,951,1785.6,2203.4,1273.3,610,622.5,915.8,852.9,784.4,654.1,617.6,836.3,1102,982.5,1516.6,1266,1535.8,1661,1460.1,291.6,348.7,266.2,1777.5,1200,639.8,1281.8,0,557.9,655.1,821.8,966.6,1139.9,1374.1,2381.7,2563.7,910.5,1847.5,2258.1,1965.7],[976.5,1152.1,1175.9,976.5,1645.5,1304.7,2139.3,2599.8,1669.7,830.6,750.3,565.6,1249.3,1138.1,1050.5,971.3,1212.2,1395.4,1254,1682.2,1396.3,1666.1,1791.3,1590.4,688,702.4,575.5,1907.8,1330.3,865.6,1444.3,561.4,0,718.3,1063.1,1096.9,1270.2,1504.4,2512,2694,1040.8,2010,2382.6,2128.2],[1080,818.6,846.2,1080,1669.1,1328.3,2162.9,2623.4,1693.3,1087.6,1141.5,1092.9,1272.9,1161.7,1074.1,994.9,1256.3,1498.9,1357.5,1759.5,1473.6,1743.4,1868.6,1667.7,711.6,726,832.5,1985.1,1407.6,538.2,972.4,665.1,732.4,0,585.3,904.2,1078,1581.7,2377,2674.8,1050.5,1538.1,1948.7,1656.3],[703.6,1085.4,451.8,703.6,1703.2,1284.7,1906.6,2256.3,1326.2,1351.3,1366.5,1426.3,905.8,943,707,914.6,920.9,1122.5,981.1,1365.1,1079.2,1349,1474.2,1273.3,609.8,824.9,1010.2,1590.7,1013.2,250.1,779.8,804.9,1068.4,586.4,0,509.8,683.6,1187.3,2184.4,2376.9,656.1,1345.5,1756.1,1463.7],[436.6,1556.1,230.2,436.6,1787.2,1426.5,1736,1903.2,1154.6,1561.8,1577,1543.8,1095.3,1165.3,929.3,1136.9,558.1,772.8,640.5,943.5,657.6,927.4,1052.6,851.7,832.1,1035.4,1220.7,1169.1,591.6,586.3,829,1015.4,1185.9,1001.2,643.8,0,238.5,765.7,1773.3,1955.3,220.9,1377.1,1743.4,1500.4],[492.4,1695,348.7,492.4,1946,1585.3,1894.8,1999.7,1313.4,1720.6,1735.8,1702.6,1254.1,1324.1,1088.1,1295.7,716.9,931.6,697.8,1040,754.1,1023.9,1142,918.1,990.9,1194.2,1379.5,1265.6,688.1,732.7,827.2,1174.2,1344.7,1147.6,790.2,227.3,0,855.1,1862.7,2044.7,241.1,1237.1,1647.7,1355.3],[614.6,2143.9,845.8,614.6,2002.1,1697.4,1719.6,1598,944.8,1881.7,1896.9,1863.7,1366.2,1485.2,1249.2,1456.8,863.6,1043.7,713.4,680.8,484.2,584.9,551.3,310.8,1152,1355.3,1540.6,863.9,436,1174.1,1406.6,1335.3,1505.8,1589,1231.6,725.5,828.2,0,1334.4,1516.4,669.4,900.9,1304.5,1161],[1677.7,2333.7,1908.9,1677.7,2805.5,2497.2,2501.6,1345.9,1713,2723.2,2960,2926.8,2137.9,2433.2,2256.2,2490.1,1926.7,2106.8,1837.2,1717.5,1626.1,1481.4,945.3,1182.9,2215.1,2418.4,2603.7,1191.6,1559.8,2209.4,1673.1,2398.4,2568.9,2297.3,2125.9,1788.6,1891.3,1315.1,0,630,1732.5,874,604.7,1053.3],[1884,2890.3,2115.2,1884,3030.5,2722.2,2726.6,1570.9,1938,2948.2,3166.3,3133.1,2362.9,2658.2,2481.2,2715.1,2133,2313.1,2043.5,1923.8,1832.4,1687.7,1151.6,1389.2,2421.4,2624.7,2810,1397.9,1766.1,2443.5,2156,2604.7,2775.2,2753.2,2501,1994.9,2097.6,1521.4,732.6,0,1938.8,1430.6,1161.3,1609.9],[310.5,1654.5,356.4,310.5,1718.8,1358.1,1667.6,1834.8,1086.2,1493.4,1508.6,1475.4,1026.9,1096.9,860.9,1068.5,489.7,704.4,538.1,875.1,589.2,859,984.2,783.3,763.7,967,1152.3,1100.7,523.2,684.7,901.1,947,1117.5,1099.6,742.2,195,244.2,697.3,1704.9,1886.9,0,1308.7,1675,1452.6],[1233.7,1726.5,1422.2,1233.7,2677.2,2316.5,2414.6,1702.1,1639.8,2402.6,2445.4,2407.9,1985.3,2104.3,1868.3,2075.9,1482.7,1662.8,1393.2,1375.8,1182.1,997.8,690.8,688.2,1771.1,1903.8,2089.1,1095.2,1115.8,1460.5,951.2,1883.8,2050,1548.4,1377,1335.7,1205.8,837.3,948.4,1348.6,1285.8,0,520.1,358.8],[1656.1,2007.2,1844.6,1656.1,2935.8,2627.5,2631.9,1766.4,1843.3,2775.1,2829,2780.4,2268.2,2526.7,2290.7,2498.3,1905.1,2085.2,1815.6,1730,1604.5,1420.2,957.8,1110.6,2193.5,2326.2,2511.5,1204.1,1538.2,1882.9,1346.6,2306.2,2422.5,1970.8,1799.4,1758.1,1628.2,1259.7,675.4,1075.6,1708.2,547.5,0,687.3],[1388.7,1750.6,1537.5,1388.7,2838.1,2477.4,2671.7,1959.2,1896.9,2517.9,2560.7,2523.2,2146.2,2239.9,2003.9,2211.5,1637.7,1823.7,1532.5,1632.9,1439.2,1254.9,947.9,945.3,1906.7,2019.1,2204.4,1352.3,1372.9,1575.8,1066.5,1999.1,2165.3,1663.7,1492.3,1451,1321.1,1094.4,1101.4,1501.6,1401.1,346.4,664.6,0]]

# Day 1 - Start at 8:00am at Location 1 (index 0)
# Day 1 - End at 4:00pm at Location 2 (index 1)
# Day 2 - Start at 6:00am at Location 3 (index 2)
# Day 2 - End at 6:00pm at Location 4 (index 3)
Windows = [[28800, 28800], [57600, 57600], [21600, 21600], [64800, 64800], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400], [0, 86400]]

Durations = [0, 0, 0, 0, 0, 0, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 900, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 3600, 3600, 3600, 3600, 3600]

Penalties = [576460752303423487, 576460752303423487, 576460752303423487, 576460752303423487, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000]

NUM_DAYS = 2

START_NODES = []
for node in range(0, NUM_DAYS):
  START_NODES.append(node * 2)

END_NODES = []
for node in range(0, NUM_DAYS):
  END_NODES.append(node * 2 + 1)

REGULAR_NODES = []
for node in range(NUM_DAYS * 2, len(Matrix)):
  REGULAR_NODES.append(node)

def transit_callback(from_index, to_index):

  # Returns the travel time between the two nodes.
  # Convert from routing variable Index to time matrix NodeIndex.
  from_node = manager.IndexToNode(from_index)
  to_node = manager.IndexToNode(to_index)

  # prevent movement from start nodes to start nodes
  if from_node in START_NODES:
    if to_node in START_NODES:
      return 576460752303423487

  # prevent movement from start nodes to end nodes
  if from_node in START_NODES:
    if to_node in END_NODES:
      return 576460752303423487

  # prevent movement from end nodes to end nodes
  if from_node in END_NODES:
    if to_node in END_NODES:
      return 576460752303423487

  # prevent movement from end nodes to non start nodes
  if from_node in END_NODES:
    if to_node  in START_NODES:
      return 0
    else:
      return 576460752303423487

  return Matrix[from_node][to_node]

def time_callback(from_index, to_index):

  # Returns the travel time plus service time between the two nodes.
  # Convert from routing variable Index to time matrix NodeIndex.
  from_node = manager.IndexToNode(from_index)
  to_node = manager.IndexToNode(to_index)

  if from_node in END_NODES:
    Reset = Windows[from_node][1]
  else:
    Reset = 0

  return Matrix[from_node][to_node] + Durations[from_node] - Reset

# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(Matrix), 1, [0], [1])

# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)

# Register the Transit Callback.
transit_callback_index = routing.RegisterTransitCallback(transit_callback)

# Set the arc cost evaluator for all vehicles
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Register the Time Callback.
time_callback_index = routing.RegisterTransitCallback(time_callback)

# Add Time Windows constraint.
routing.AddDimension(
  time_callback_index,
  86400, # An upper bound for slack (the wait times at the locations).
  86400, # An upper bound for the total time over each vehicle's route.
  False,
  'Time')
time_dimension = routing.GetDimensionOrDie('Time')

# Get rid of slack for all regular nodes
# for node in range(len(START_NODES) + len(END_NODES), len(Matrix)):
#   index = manager.NodeToIndex(node)
#   time_dimension.SlackVar(index).SetValue(0)

# Get rid of slack for all start nodes
# for node in START_NODES:
#   index = manager.NodeToIndex(node)
#   time_dimension.SlackVar(index).SetValue(0)

# Allow all regular nodes to be droppable.
for node in range(len(START_NODES) + len(END_NODES), len(Matrix)):
  routing.AddDisjunction([manager.NodeToIndex(node)], Penalties[node])

# Add time window constraints for all regular nodes.
for location_index, time_window in enumerate(Windows):
  if location_index in REGULAR_NODES:
    index = manager.NodeToIndex(location_index)
    time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

# TODO! - I think this needs to be handled differently for each day
# Add time window constraints for start node.
index = routing.Start(0)
time_dimension.CumulVar(index).SetRange(Windows[0][0],Windows[0][1])
index = routing.End(0)
time_dimension.CumulVar(index).SetRange(Windows[1][0],Windows[1][1])

# Setting first solution heuristic. 
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION)

# Setting local search metaheuristics:
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 15
search_parameters.log_search = False

# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
if not solution:
  print("no solution found")
else:
  print("solution found.  Objective value is ",solution.ObjectiveValue())

  # Print the results
  result = {
    'Dropped': [],
    'Scheduled': []
  }

  # Return the dropped locations
  for index in range(routing.Size()):
    if routing.IsStart(index) or routing.IsEnd(index):
      continue
    node = manager.IndexToNode(index)
    if node in END_NODES or node in START_NODES:
      continue
    if solution.Value(routing.NextVar(index)) == index:
      result['Dropped'].append(node)

  # Return the scheduled locations
  time = 0
  index = routing.Start(0)
  while not routing.IsEnd(index):
    time = time_dimension.CumulVar(index)
    result['Scheduled'].append([manager.IndexToNode(index), solution.Min(time), solution.Max(time)])
    index = solution.Value(routing.NextVar(index))
  time = time_dimension.CumulVar(index)
  result['Scheduled'].append([manager.IndexToNode(index), solution.Min(time), solution.Max(time)])

  print('Dropped')
  print(result['Dropped'])

  print('Scheduled')
  for line in result['Scheduled']:
    print(line)

Output:

solution found.  Objective value is  22468
Dropped
[]
Scheduled
[0, 28800, 28800]
[28, 29216, 35021]
[20, 31277, 37082]
[21, 33510, 39315]
[19, 35787, 41592]
[8, 37197, 43002]
[6, 39278, 45083]
[4, 40829, 46634]
[5, 41386, 47191]
[9, 42037, 47842]
[26, 43496, 49301]
[10, 45818, 51623]
[11, 47690, 53495]
[32, 49169, 54974]
[31, 51530, 57335]
[24, 53621, 59426]
[25, 55790, 61595]
[15, 57982, 63787]
[13, 59251, 65056]
[14, 60366, 66171]
[12, 61559, 67364]
[17, 62886, 68691]
[16, 64245, 70050]
[18, 65428, 71233]
[3, 66607, 72412]
[2, 2334, 8139]
[35, 2530, 8335]
[36, 4568, 10373]
[40, 6609, 12414]
[37, 10906, 16711]
[23, 13016, 18821]
[22, 15163, 20968]
[27, 17473, 23278]
[7, 20179, 25984]
[39, 22710, 28515]
[38, 27042, 32847]
[42, 29446, 35251]
[41, 33593, 39398]
[43, 37551, 43356]
[30, 42217, 48022]
[34, 44789, 50594]
[29, 46839, 52644]
[33, 49177, 54982]
[1, 57600, 57600]

Calash answered 26/11, 2020 at 20:38 Comment(2)

I don't see something that is wrong on first sight, at least not something that is obvious. Have you tried relaxing the constraints? Start with relaxing all constraints and re-activate them one by one to see what may cause a problem. Start by increasing capacity and max slack to something very large (e.g. 1e10). Also, set log_search=Trueand increase the local search heuristic time. Just run it for 30 minutes and see if still finds solutions. Aside from that I wouldn't recommend modelling your problem with a start time at 0. (1/2) – Destructionist 1/12, 2020 at 15:10

It is better to model using your own domain models that map to the problem you are solving. This way you can keep track of times, vehicles and locations in a way that makes sense to a human (proper date times, coordinates, etc.). Then you can convert that to the OR-Tools model and map it back and make sense of the solution. Note: for time I would recommend using epoch time, that way you can easily model using a longer time horizon. Hope this helps (2/2) – Destructionist 1/12, 2020 at 15:13

You may have something like that:

python plop.py
Objective: 93780
droped: []
Route for vehicle 0:
0 [21600;21600] -> 38 [21902;57722] -> 33 [23897;59717] -> 34 [25935;61755] -> 28 [28562;64382] -> 41 [31374;67194] -> 39 [33520;69340] -> 40 [35840;71660] -> 36 [38315;74135] -> 37 [40745;76565] -> 5 [44115;79935] -> 25 [46810;82630] -> 20 [49163;84983] -> 21 [51370;790+1day] -> 35 [53471;2891+1day] -> 26 [55707;5127+1day] -> 18 [57768;7188+1day] -> 19 [60001;9421+1day] -> 17 [62278;11698+1day] -> 6 [64588;14008+1day] -> 4 [67569;16989+1day] -> 2 [70020;19440+1day] -> 3 [72377;21797+1day] -> 7 [74828;24248+1day] -> 24 [77187;26607+1day] -> 8 [79509;28929+1day] -> 9 [82281;31701+1day] -> 30 [84660;34080+1day] -> 31 [778+1day;36598+1day] -> 32 [3163+1day;38983+1day] -> 27 [5213+1day;41033+1day] -> 22 [7579+1day;43399+1day] -> 29 [9715+1day;45535+1day] -> 23 [11863+1day;47683+1day] -> 13 [14055+1day;49875+1day] -> 11 [16224+1day;52044+1day] -> 12 [18239+1day;54059+1day] -> 10 [20332+1day;56152+1day] -> 15 [22559+1day;58379+1day] -> 14 [24818+1day;60638+1day] -> 16 [26901+1day;62721+1day] -> 1 [64800+1day;64800+1day]

%diff -u plop.py plop_final.py 
--- plop.py 2020-12-01 17:48:15.187255138 +0100
+++ plop_final.py   2020-12-01 17:47:41.033692899 +0100
@@ -7,6 +7,7 @@
 Penalties = [576460752303423487, 576460752303423487, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000]
 Slack_Max = 86400
 Capacity = 86400
+OneDay = 86400
 
 # The inputs to RoutingIndexManager are:
 #   1. The number of rows of the time matrix, which is the number of locations (including the depot).
@@ -36,7 +37,7 @@
 routing.AddDimension(
     transit_callback_index,
     Slack_Max,  # An upper bound for slack (the wait times at the locations).
-    Capacity,  # An upper bound for the total time over each vehicle's route.
+    2*Capacity,  # An upper bound for the total time over each vehicle's route.
     False,  # Determine whether the cumulative variable is set to zero at the start of the vehicle's route.
     'Time')
 time_dimension = routing.GetDimensionOrDie('Time')
@@ -50,13 +51,14 @@
   if location_idx == 0 or location_idx == 1:
     continue
   index = manager.NodeToIndex(location_idx)
-  time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
+  time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1]+OneDay)
+  time_dimension.CumulVar(index).RemoveInterval(time_window[1], time_window[0]+OneDay)
 
 # Add time window constraints for each vehicle start node.
 index = routing.Start(0)
 time_dimension.CumulVar(index).SetRange(Windows[0][0],Windows[0][1])
 index = routing.End(0)
-time_dimension.CumulVar(index).SetRange(Windows[1][0],Windows[1][1])
+time_dimension.CumulVar(index).SetRange(Windows[1][0]+OneDay,Windows[1][1]+OneDay)
 
 # Instantiate route start and end times to produce feasible times.
 routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(0)))
@@ -73,28 +75,24 @@
 
 # Solve the problem.
 solution = routing.SolveWithParameters(search_parameters)
-
-# Print the results
-result = {
-  'Dropped': [],
-  'Scheduled': []
-}
+print(f"Objective: {solution.ObjectiveValue()}")
 
 # Return the dropped locations
+dropped = []
 for node in range(routing.Size()):
   if routing.IsStart(node) or routing.IsEnd(node):
     continue
   if solution.Value(routing.NextVar(node)) == node:
-    result['Dropped'].append(manager.IndexToNode(node))
+    dropped.append(manager.IndexToNode(node))
+print(f"droped: {dropped}")
 
 # Return the scheduled locations
-time = 0
 index = routing.Start(0)
+plan_output = 'Route for vehicle 0:\n'
 while not routing.IsEnd(index):
   time = time_dimension.CumulVar(index)
-  result['Scheduled'].append([manager.IndexToNode(index), solution.Min(time),solution.Max(time)])
+  tw_min = solution.Min(time)
+  if tw_min > OneDay:
+      tw_min = f"{tw_min%OneDay}+1day"
+  tw_max = solution.Max(time)
+  if tw_max > OneDay:
+      tw_max = f"{tw_max%OneDay}+1day"
+
+  plan_output += f'{manager.IndexToNode(index)} [{tw_min};{tw_max}] -> '
   index = solution.Value(routing.NextVar(index))
 time = time_dimension.CumulVar(index)
-result['Scheduled'].append([manager.IndexToNode(index), solution.Min(time),solution.Max(time)])
-
-print(result)
+tw_min = solution.Min(time)
+tw_max = solution.Max(time)
+if tw_min > OneDay:
+    tw_min = f"{tw_min%OneDay}+1day"
+tw_max = solution.Max(time)
+if tw_max > OneDay:
+    tw_max = f"{tw_max%OneDay}+1day"
+plan_output += f'{manager.IndexToNode(index)} [{tw_min};{tw_max}]'
+print(plan_output)

My changes:

Add const OneDay = 86400
Change Vehicle horizon to two day i.e. Capacity+OneDay
You can remove a range of value using RemoveInterval() method.
ref: https://github.com/google/or-tools/blob/84c35244c9bdd635609af703bbf3053c16c487c0/ortools/constraint_solver/constraint_solver.h#L3980-L3988
So the idea is SetRange to [FirstTW start; LastTW end] then remove [FirstTW end; LastTW start]
Then I rewrite the output part (cleaner to me by removing your "unused struct result for this snippet")

ps: If you have question, please join our or-tools discord (link in the README on github) ;)

Step 2

Currently:

your TW for location is [0;86400] while your vehicle is working from 21600 to 64800.
Your end TW is [64800, 64800] instead I would use [21600;64800] i.e. finish ASAP instead of dispatching visit until 6pm ?

So let's hack your TW data as follow:

Windows = [[21600, 21600], [21600, 64800], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400], [21600, 86400]]

Then you'll get the following result:

python plop_final.py
Objective: 93780
droped: []
Route for vehicle 0:
0 [21600;21600] -> 38 [21902;23641] -> 33 [23897;25636] -> 34 [25935;27674] -> 28 [28562;30301] -> 41 [31374;33113] -> 39 [33520;35259] -> 40 [35840;37579] -> 36 [38315;40054] -> 37 [40745;42484] -> 5 [44115;45854] -> 25 [46810;48549] -> 20 [49163;50902] -> 21 [51370;53109] -> 35 [53471;55210] -> 26 [55707;57446] -> 18 [57768;59507] -> 19 [60001;61740] -> 17 [62278;64017] -> 6 [64588;66327] -> 4 [67569;69308] -> 2 [70020;71759] -> 3 [72377;74116] -> 7 [74828;76567] -> 24 [77187;78926] -> 8 [79509;81248] -> 9 [82281;84020] -> 30 [84660;86399] -> 31 [21601+1day;21601+1day] -> 32 [23986+1day;23986+1day] -> 27 [26036+1day;26036+1day] -> 22 [28402+1day;28402+1day] -> 29 [30538+1day;30538+1day] -> 23 [32686+1day;32686+1day] -> 13 [34878+1day;34878+1day] -> 11 [37047+1day;37047+1day] -> 12 [39062+1day;39062+1day] -> 10 [41155+1day;41155+1day] -> 15 [43382+1day;43382+1day] -> 14 [45641+1day;45641+1day] -> 16 [47724+1day;47724+1day] -> 1 [49803+1day;49803+1day]

note: You can find my fork here: https://github.com/Mizux/tsp_multiple_days

Immerge answered 1/12, 2020 at 16:51 Comment(2)

I appreciate the response @Immerge - I'll continue to poke around and keep you in the loop. I tried my best to find this Discord you mentioned, but no dice; would you mind sharing that with me? – Calash 1/12, 2020 at 22:54

github.com/google/or-tools/blob/stable/README.md simply click on the "chat" button url should be discord.com/invite/ENkQrdf – Immerge 1/12, 2020 at 23:34

Follow up with my solution, which is also available on GitHub.

The nature of my original question was pretty particular - my goal was to make locations in the traveling salesperson problem available for recurring time windows each day over an arbitrary number of days (i.e. making a location only available between 2:00pm - 4:00pm during each day over the span of some days that the vehicle would be active).

The solution came down to modeling the problem in a way such that the entire span of days would be represented as one large range of time between the start of the first day and the end of the last day; all durations of unavailability (due to night time, existing events, unavailable time windows, etc) would be removed from this range. This was achieved by using SetRange and RemoveInterval.

I've included the Google OR-Tools python library implementation below, but my sample data is too large, so it will remain available in the repository that I previously linked to above.

from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
import math
import sys
import json

# Specify the JSON data file
with open('3_days_60_locations.json') as file:
    event = json.load(file)

Locations = event['Locations']
Matrix = event['Matrix']
Windows = event['Windows']
ServiceCosts = event['ServiceCosts']
Penalties = event['Penalties']
NUM_DAYS = event['NumberOfDays']
NUM_EVENTS = event['NumberOfEvents']
DURATION = event['Duration']
ONE_DAY = 86400

def transit_callback(from_index, to_index):
    # Returns the travel time plus service time between the two nodes.
    # Convert from routing variable Index to time matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return Matrix[from_node][to_node] + ServiceCosts[from_node]

# Create the routing index manager.
# Start is the start location of the first day
# End is the end location of the last day
manager = pywrapcp.RoutingIndexManager(len(Matrix), 1, [0], [2*NUM_DAYS-1])

# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)

# Register the Transit Callback.
transit_callback_index = routing.RegisterTransitCallback(transit_callback)

# Set the arc cost evaluator for all vehicles
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Add Time Windows constraint.
routing.AddDimension(
    transit_callback_index,
    ONE_DAY * NUM_DAYS, # An upper bound for slack (the wait times at the locations).
    ONE_DAY * NUM_DAYS, # An upper bound for the total time over each vehicle's route.
    False, # Determine whether the cumulative variable is set to zero at the start of the vehicle's route.
    'Time')
time_dimension = routing.GetDimensionOrDie('Time')

# Allow locations to be droppable.
# Do not allow the start location of the first day to be droppable.
# Do not allow the end location of the last day to be droppable.
for node in range(0, len(Matrix)):
    if node != 0 and node != (2 * NUM_DAYS) - 1:
        routing.AddDisjunction([manager.NodeToIndex(node)], Penalties[node])

# Add time window constraints for all start and end locations.
for i in range(0, NUM_DAYS*2):
    if i == 0:
        index = routing.Start(0)
    elif i == NUM_DAYS*2 - 1:
        index = routing.End(0)
    else:
        index = manager.NodeToIndex(i)
    time_dimension.CumulVar(index).SetRange(Windows[i][0],Windows[i][1])

# Add time window constraints for all additional event locations.
for location_index, time_window in enumerate(Windows):
    if location_index in range(NUM_DAYS * 2, NUM_DAYS * 2 + NUM_EVENTS):
        index = manager.NodeToIndex(location_index)

        # Add the range between the start of the first day and the end of the last day
        time_dimension.CumulVar(index).SetRange(Windows[location_index][0],Windows[location_index][1])

# Add time window constraints for all regular locations.
for location_index, time_window in enumerate(Windows):
    if location_index in range(NUM_DAYS * 2 + NUM_EVENTS, len(Matrix)):
        index = manager.NodeToIndex(location_index)

        # Add the range between the start of the first day and the end of the last day
        time_dimension.CumulVar(index).SetRange(0, 86400 * NUM_DAYS)

        for Day in range(NUM_DAYS):

            Day_Start = Day * ONE_DAY
            Day_End = Day_Start + ONE_DAY
            Working_Start = Windows[Day * 2][0]
            Working_End =   Windows[Day * 2 + 1][0]

            # Remove the range between the start of the day and the start of work
            time_dimension.CumulVar(index).RemoveInterval(Day_Start, Working_Start)

            # Remove the range between the start of the day and the start of location
            time_dimension.CumulVar(index).RemoveInterval(Day_Start, Day_Start + time_window[0])

            # Remove the range between the end of work and the end of the day
            time_dimension.CumulVar(index).RemoveInterval(Working_End, Day_End)

            # Remove the range between the end of location and the end of the day
            time_dimension.CumulVar(index).RemoveInterval(Day_Start + time_window[1], Day_End)

# Instantiate route start and end times to produce feasible times
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(0)))
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(0)))

# Setting first solution heuristic. 
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.ALL_UNPERFORMED)

# Setting local search metaheuristics:
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = DURATION
search_parameters.log_search = False

# Solve the problem
solution = routing.SolveWithParameters(search_parameters)

if not solution:
    print("No solution found !")
    sys.exit(1)

result = {
    'DroppedLocations': [],
    'ScheduledLocations': []
}

# Return dropped locations
for node in range(routing.Size()):
    if routing.IsStart(node) or routing.IsEnd(node):
        continue
    if solution.Value(routing.NextVar(node)) == node:
        index = manager.IndexToNode(node)
        result['DroppedLocations'].append(Locations[index])

# Return scheduled locations
index = routing.Start(0)
while not routing.IsEnd(index):
    time = time_dimension.CumulVar(index)
    Location = Locations[manager.IndexToNode(index)]
    Location['earliestArrivalTime'] = solution.Min(time);
    Location['latestArrivalTime'] = solution.Max(time);
    result['ScheduledLocations'].append(Location)
    index = solution.Value(routing.NextVar(index))
time = time_dimension.CumulVar(index)
Location = Locations[manager.IndexToNode(index)]
Location['earliestArrivalTime'] = solution.Min(time);
Location['latestArrivalTime'] = solution.Max(time);
result['ScheduledLocations'].append(Location)

print(result)

Calash answered 23/12, 2020 at 5:4 Comment(0)

Hot tags

Godot Unity Godot Help Programming Godot 4.X GUI GDScript 3D 2D Physics CSharp Godot 3.X VR XR Projects C++

Step 2

Recommended topics

Hot tags