TSP - Span multiple days with start/stop times

[Josh Kautz]

I have also posted this question on Stack Overflow with a bounty.

I have been using Google OR-Tools to optimize routing of a single vehicle over the span of a single day. I have included the code below, which runs in Python 3.

The time matrix I have included represents 42 locations; the first two locations are the depot where the vehicle will begin and end the day (these won't necessarily always be the same location). The remaining forty locations all represent McDonald's restaurants in the Minneapolis area. The vehicle cannot leave the depot until 6:00am (21600 seconds), and must return to the depot by 6:00pm (64800 seconds). I do have time windows enforced for visits to the locations, but for the sake of brevity and simplicity in my question, I've allowed the locations to be visited at any time (while still meeting the condition of beginning and ending the day at 6:00am and 6:00pm, respectively). Additionally, every location must be visited for a duration of 30 minutes (1800 seconds).

When I run my implementation, there are (as you'd expect) many locations that are not visited, due to all of the existing constraints. I want to modify my solution to allow for schedules to be created across multiple days. For example, I would like my implementation to explore solutions where the locations are schedule to be visited the following day as well, starting at 6:00am (21600 seconds + 86400 seconds) and ending at 6:00pm (64800 seconds + 86400 seconds). I also want to allow for disjointed time windows, though I'm afraid that may be too much to ask for someone to help me with at once. I have attempted this on my own, but my efforts have been fruitless and yielded only errors. I thought sharing my working solution and my constraints would be a good place to start when asking for help, but I'd be more than happy to provide any additional context and information I may have omitted.

I have already referenced the following resources:

• Multiple time windows for vehicle routing problem instance #167
• VRP with Time Windows - More than 1 time window per location #456
• Multiple Time Windows per Location, and Vehicle Specialties & Replenishment
• Multiple time windows vrp [or-tools]

Are there any blatant errors in my usage of OR Tools? I'm happy to answer any questions. Any help will be very appreciate! Thank you!

I have also posted this question on Stack Overflow with a bounty.

Source:

from ortools.constraint_solver import pywrapcp

from ortools.constraint_solver import routing_enums_pb2

Matrix = [[0,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],[0,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,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,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,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,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,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,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,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,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,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,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,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,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,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.8,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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,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]]

Windows = [[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, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800, 1800]

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

# The inputs to RoutingIndexManager are:

# 1. The number of rows of the time matrix, which is the number of locations (including the depot).

# 2. The number of vehicles in the problem.

# 3. The node corresponding to the depot.

# Create the routing index manager.

manager = pywrapcp.RoutingIndexManager(len(Matrix), 1, [0], [1])

# Create Routing Model.

routing = pywrapcp.RoutingModel(manager)

# Create and register a transit callback.

def time_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)

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

transit_callback_index = routing.RegisterTransitCallback(time_callback)

# Define cost of each arc.

routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Add Time Windows constraint.

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.

   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 all locations except the first two to be droppable.

for node in range(2, len(Matrix)):

   routing.AddDisjunction([manager.NodeToIndex(node)], Penalties[node])

# Add time window constraints for each location except depot.

for location_idx, time_window in enumerate(Windows):

   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])

# 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])

# 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.PATH_CHEAPEST_ARC)

# Setting local search metaheuristics:

search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

search_parameters.time_limit.seconds = 5

search_parameters.log_search = False

# Solve the problem.

solution = routing.SolveWithParameters(search_parameters)

# Print the results

result = {

   'Dropped': [],

   'Scheduled': []

}

# Return the dropped locations

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))

# 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(result)

Output:

{'Dropped': [5, 8, 9, 20, 21, 22, 25, 27, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41], 'Scheduled': [[0, 21600, 21600], [14, 21964, 21982], [15, 24235, 24253], [10, 26468, 26486], [12, 28494, 28512], [11, 30568, 30586], [13, 32677, 32695], [23, 34869, 34887], [29, 37037, 37055], [24, 39103, 39121], [7, 41413, 41431], [3, 43898, 43916], [2, 46266, 46284], [4, 48674, 48692], [6, 51672, 51690], [17, 53921, 53939], [19, 56163, 56181], [18, 58543, 58561], [26, 60553, 60571], [16, 62703, 62721], [1, 64800, 64800]]}

[soumojit kumar]

Hello,

 I am trying to solve a MIP problem using OR-Tools/Python combination. I am creating the solver instance by this:

# Create the mip solver with the CBC backend.
solver = pywraplp.Solver('berth_or_tools', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

solver.EnableOutput()
solver.SetTimeLimit(7200000)
solver.log_search_progress = True
solver.num_search_workers = 8

However, I am finding issues to set MIP GAP, Presolve, Heuristics parameters as that can be set in other commercial solvers. Again, during the optimization process, I wish to see the path in which the optimization is proceeding. It is not showing dynamically, once the time limit is over, it is just burping the dump. Can you help to correct these issues?

With regards, 

Soumojit Kumar

FRM (GARP, USA), B.E.E. (JU)
Fellow in Management (PhD), IIM Calcutta

Phone(Mob): +91-7003578304

          

[soumojit kumar]

[Laurent Perron]

you are mixing the CP-SAT api and the linear solver API.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAOANqm8K4Pd2E9SjG5OqQhkEBHSb6YfX-14fb0VQ%3Dv0SfhQSLQ%40mail.gmail.com.

[Laurent Perron]

http://google.github.io/or-tools/python/ortools/linear_solver/pywraplp.html#pywraplp.MPSolverParameters

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[blind.lin...@gmail.com]

Hi Josh,

(This thread got split in the forum...This is a reply to Josh about
the multi-day TSP question)

I modified your code and got it to work for multiple days. But
assuming you'd rather figure this out on your own, here are my
suggestions.

First, I recommend using a few more abstractions...I found it a bit
difficult to deal with all of the long arrays of identical things
(operating hours for nodes, etc).

The key insight I think is to recognize that "time" isn't really a
thing in OR Tools. It is just a dimension, and dimensions are just
accumulators. So my approach is to treat it like the "cvrp_reload.py"
example, especially where the vehicles are "unloaded" at the depot by
giving the depot nodes a negative demand
(https://github.com/google/or-tools/blob/d8f1f6d54edbfdf292a4bc690b6c925b9d1d4527/ortools/constraint_solver/samples/cvrp_reload.py#L73).

Another important point is that you will have to make additional
"depot nodes", one per day, in order to simulate the vehicle returning
to base for the night. Each of these will need to "reset" the time
dimension, as is done in the reload example.

Next, you'll need to keep better track of nodes and dummy nodes. This
is because when you create dummy nodes for the overnight depot visits,
you will have to convert those nodes to node 1 in order to look them
up in the distance matrix properly.

Moving along in your code, I think you should separate out the
per-link cost, and the time-elapsed calculation. The per-link
function should be used as the arc cost evaluator. The total time
elapsed function should be used as the callback function for time.
When time increases monotonically, the two are basically the same.
But when your "service time" includes large negative numbers that
reset time, then the solver will get confused...it will try to
minimize something that drops with every visit back to the overnight
depots.

This is done in the example. Notice at line 324
(https://github.com/google/or-tools/blob/d8f1f6d54edbfdf292a4bc690b6c925b9d1d4527/ortools/constraint_solver/samples/cvrp_reload.py#L324)
that the call to
SetArcCostEvaluatorOfAllVehicles uses the "distance" callback, not the
"time" callback. The time is the combination of distance/speed plus
service time. But the distance is strictly the travel between nodes,
ignoring any service time.

On the time window constraints, I'd set the time windows of all of the
nodes to 6am and 6pm, because you can't get there any earlier or leave
any later, so why not make the solver's job a smidge easier. Then,
rather than using set range, I'd use SetMin() for the depot, SetMax
for the return node (node 1), because I think it is cleaner that way.

In my solution I also created a "counting dimension" in order to keep
straight the order of nodes (since time is no longer monotonically
increasing). Something like:

num_nodes = len(Matrix)
night_nodes = range(num_nodes, num_nodes+num_days)
total_nodes = num_nodes + len(night_nodes) # == num_nodes + num_days

routing.AddConstantDimension(1, # increment by 1
total_nodes+1, # will never hit this limit (1 more than visiting every node)
True, # start count at zero
"Counting")
count_dimension = routing.GetDimensionOrDie('Counting')


This isn't really necessary, but depending what you do going forward,
it may help to keep track what day you're on.

Again, I have a working solution, but I'm guessing you'd rather work
it out yourself. If you just want the answer, let me know. I'm
thinking about writing it up and posting it to my blog, but I
sometimes get sidetracked and don't finish those blog posts.

(I don't really want to know why you'd want to visit every McD in the
Minneapolis area.)

Hope that helps,

James


On Sat, Nov 28, 2020 at 01:52:16PM -0800, or-tools wrote:
>
>
> *I have also posted this question on Stack Overflow
> <https://stackoverflow.com/questions/65028943/google-or-tools-tsp-spanning-multiple-days-with-start-stop-times> with
> a bounty.*

>
> I have been using Google OR-Tools to optimize routing of a single vehicle
> over the span of a single day. I have included the code below, which runs
> in Python 3.
>
> The time matrix I have included represents 42 locations; the first two
> locations are the depot where the vehicle will begin and end the day (these
> won't necessarily always be the same location). The remaining forty
> locations all represent McDonald's restaurants in the Minneapolis area. The
> vehicle cannot leave the depot until 6:00am (21600 seconds), and must
> return to the depot by 6:00pm (64800 seconds). I do have time windows
> enforced for visits to the locations, but for the sake of brevity and
> simplicity in my question, I've allowed the locations to be visited at any
> time (while still meeting the condition of beginning and ending the day at
> 6:00am and 6:00pm, respectively). Additionally, every location must be
> visited for a duration of 30 minutes (1800 seconds).
>
> When I run my implementation, there are (as you'd expect) many locations
> that are not visited, due to all of the existing constraints. I want to
> modify my solution to allow for schedules to be created across multiple
> days. For example, I would like my implementation to explore solutions
> where the locations are schedule to be visited the following day as well,
> starting at 6:00am (21600 seconds + 86400 seconds) and ending at 6:00pm

> (64800 seconds + 86400 seconds). I also want to allow for *disjointed time
> windows
> <https://github.com/google/or-tools/blob/master/examples/cpp/cvrp_disjoint_tw.cc>*,

> though I'm afraid that may be too much to ask for someone to help me with
> at once. I have attempted this on my own, but my efforts have been
> fruitless and yielded only errors. I thought sharing my working solution
> and my constraints would be a good place to start when asking for help, but
> I'd be more than happy to provide any additional context and information I
> may have omitted.
>
> I have already referenced the following resources:
>

> - Multiple time windows for vehicle routing problem instance #167
> <https://github.com/google/or-tools/issues/167>
> - VRP with Time Windows - More than 1 time window per location #456
> <https://github.com/google/or-tools/issues/456>
> - Multiple Time Windows per Location, and Vehicle Specialties &
> Replenishment
> <https://groups.google.com/g/or-tools-discuss/c/MBq1TcqSQTI?pli=1>
> - Multiple time windows vrp [or-tools]
> <https://stackoverflow.com/questions/61456895/multiple-time-windows-vrp-or-tools>

>
> Are there any blatant errors in my usage of OR Tools? I'm happy to answer
> any questions. Any help will be very appreciate! Thank you!

> *I have also posted this question on Stack Overflow
> <https://stackoverflow.com/questions/65028943/google-or-tools-tsp-spanning-multiple-days-with-start-stop-times> with
> a bounty.*
>
> *Source
> <https://gist.github.com/joshykautz/04b458558935845cc1d5cb81797de862>:*

> *Output
> <https://gist.github.com/joshykautz/04b458558935845cc1d5cb81797de862>:*

> {'Dropped': [5, 8, 9, 20, 21, 22, 25, 27, 28, 30, 31, 32, 33, 34, 35, 36,
> 37, 38, 39, 40, 41], 'Scheduled': [[0, 21600, 21600], [14, 21964, 21982],
> [15, 24235, 24253], [10, 26468, 26486], [12, 28494, 28512], [11, 30568,
> 30586], [13, 32677, 32695], [23, 34869, 34887], [29, 37037, 37055], [24,
> 39103, 39121], [7, 41413, 41431], [3, 43898, 43916], [2, 46266, 46284], [4,
> 48674, 48692], [6, 51672, 51690], [17, 53921, 53939], [19, 56163, 56181],
> [18, 58543, 58561], [26, 60553, 60571], [16, 62703, 62721], [1, 64800,
> 64800]]}
>

> --
> You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/793d6be3-ffcd-41c0-920c-9e3fe2fe2c1dn%40googlegroups.com.


--

James E. Marca
Activimetrics LLC

[Josh Kautz]

James,

Thank you so much for the thorough response, I really appreciate your time! I am spending some time this afternoon here to really look at the cvrp_reload.py example. The majority of what you said makes plenty of sense to me conceptually; I omitted all of my attempts from the original post because I thought that would be helpful for people to try helping me. My first step is indeed adding one additional node (stop/start location) for each additional day. I'm happy to play around with handling how to reset  the time dimension in between each day.

I'll continue chugging along on this on my own, for the sake of learning and independence, but I certainly wouldn't mind being able to take a look at your solution as a resource to better understand Google's OR-Tools can be used; if you steer me in the direction of your blog I'd be happy to read and support you!

Again, thank you for your time and involvement in the community - we really do appreciate your willingness to share your knowledge!

Sincerely,

Josh

[blind.lin...@gmail.com]

I accomplish the reset as follows:

```
node_service_time = 1800
overnight_time = -18*3600
Slack_Max = 3600 * 24 # one day
Capacity = 3600 * 24 # one day

...
def time_callback(from_index, to_index):
# Returns the travel 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)

# service time is 0 if start or end depot, node_service_time if a node, and overnight_time if an overnight node
_service_time = node_service_time
if from_node == 0 or from_node==1:
_service_time = 0
if from_node in night_nodes:
_service_time = overnight_time

# adjust if either node is a night node
if from_node >= num_nodes:
from_node = 1
if to_node >= num_nodes:
to_node = 1

return Matrix[from_node][to_node] + _service_time

time_callback_index = routing.RegisterTransitCallback(time_callback)

# create time dimension
routing.AddDimension(
time_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.
False, # Determine whether the cumulative variable is set to zero at the start of the vehicle's route.
'Time')
time_dimension = routing.GetDimensionOrDie('Time')

```

On Sun, Nov 29, 2020 at 10:57:10AM -0800, or-tools wrote:
> James,
> Thank you so much for the thorough response, I really appreciate your time!
> I am spending some time this afternoon here to really look at the
> cvrp_reload.py

> <https://github.com/google/or-tools/blob/d8f1f6d54edbfdf292a4bc690b6c925b9d1d4527/ortools/constraint_solver/samples/cvrp_reload.py#L177-L184>example.

> The majority of what you said makes plenty of sense to me conceptually; I
> omitted all of my attempts from the original post because I thought that
> would be helpful for people to try helping me. My first step is indeed

> adding *one* additional node (stop/start location) for each additional day.
> I'm happy to play around with handling how to *reset* the time dimension

> in between each day.
>
> I'll continue chugging along on this on my own, for the sake of learning

> and independence, but I certainly *wouldn't *mind being able to take a look

> To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/9c7a63ef-7760-4d50-ba80-15c7d970a1a7n%40googlegroups.com.

[Miguel Marengo]

Hi Josh,

I have exactly the same question you have. Even with the tips you have received, I haven't been able to do multiday deliveries.

If you happened to resolve it, I would love to see your final code. 

Thank you for being so clear with your code!!!

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/793d6be3-ffcd-41c0-920c-9e3fe2fe2c1dn%40googlegroups.com.

This message (and any associated files) may contain confidential and/or privileged information. If you are not the intended recipient or authorized to receive this for the intended recipient, you must not use, copy, disclose or take any action based on this message or any information herein. If you have received this message in error, please advise the sender immediately by sending a reply e-mail and delete this message. Thank you for your cooperation.

[blind.lin...@gmail.com]

I posted my edits to Josh's original to github.

I'll finish up my write up tomorrow, but just in case I don't I wanted to get this up.

Link is https://github.com/jmarca/tsp_multiple_days

Mostly just hacking here and there to solve the problem of running the TSP over multiple days.

The latest branch is "feature/morning_nodes", in which I add additional nodes for mornings.

A sample solution without the morning nodes looks like:

```
Scheduled
[0, 0, 6.0, 10.096944444444444]
[26, 1, 6.115555555555556, 10.2125]
[18, 2, 6.688055555555556, 10.785]
[19, 3, 7.308333333333334, 11.405277777777778]
[17, 4, 7.940833333333333, 12.037777777777778]
[6, 5, 8.5825, 12.679444444444444]
[4, 6, 9.410555555555556, 13.5075]
[2, 7, 10.091388888888888, 14.188333333333333]
[3, 8, 10.74611111111111, 14.843055555555555]
[7, 9, 11.426944444444445, 15.523888888888889]
[11, 10, 12.071944444444444, 16.16888888888889]
[10, 11, 12.663055555555555, 16.76]
[15, 12, 13.281666666666666, 17.378611111111113]
['Overnight at 51, dummy for 1', 13, 13.903055555555556, 18.0]
[42, 14, 6.0, 7.976388888888889]
[38, 15, 6.583888888888889, 8.560277777777777]
```

Note that the "overnight" node constrains the *arrival* time, not the
departure time, because that's how the slack variable works.

The node *after* the overnight node, node 42, starts at 6AM. I didn't
want that, but instead wanted the departure from the overnight node to
be at 6am.

So the morning nodes were added with some hacky logic to make sure
that the overnight nodes transitioned to the morning node at 6am, and
that the service time at the morning node is zero, so that effectively
the earliest departure from the morning node is 6am.

```
Scheduled
[0, 0, 6.0, 6.0625]
[26, 1, 6.115555555555556, 6.178055555555556]
[18, 2, 6.688055555555556, 6.750555555555556]
[17, 3, 7.313055555555556, 7.375555555555556]
[19, 4, 7.935833333333333, 7.998333333333333]
[35, 5, 8.588055555555556, 8.650555555555556]
[21, 6, 9.174166666666666, 9.236666666666666]
[20, 7, 9.770555555555555, 9.833055555555555]
[25, 8, 10.412222222222223, 10.474722222222223]
[5, 9, 11.16388888888889, 11.22638888888889]
[37, 10, 12.116944444444444, 12.179444444444444]
[36, 11, 12.820277777777777, 12.882777777777777]
[40, 12, 13.488055555555556, 13.550555555555556]
[39, 13, 14.14, 14.2025]
[41, 14, 14.739444444444445, 14.801944444444445]
[28, 15, 15.535555555555556, 15.598055555555556]
[34, 16, 16.227222222222224, 16.289722222222224]
[33, 17, 16.790277777777778, 16.852777777777778]
[38, 18, 17.351388888888888, 17.413888888888888]
['Overnight at 43, dummy for 1', 19, 17.9375, 18.0]
['Starting day at 47, dummy for 1', 20, 6.0, 11.336944444444445]
[22, 21, 6.193888888888889, 11.530833333333334]
[23, 22, 6.796388888888889, 12.133333333333333]
```

So here, with the "morning nodes", the AM travel departs from depot at
6am

Regards,
James

On Sun, Nov 29, 2020 at 08:55:41PM -0600, Miguel Marengo wrote:
> Hi Josh,
> I have exactly the same question you have. Even with the tips you have
> received, I haven't been able to do multiday deliveries.
> If you happened to resolve it, I would love to see your final code.
>
> Thank you for being so clear with your code!!!
>
> El sáb., 28 de noviembre de 2020 15:52, 'Josh Kautz' via or-tools-discuss <
> or-tools...@googlegroups.com> escribió:
>

> > *I have also posted this question on Stack Overflow
> > <https://stackoverflow.com/questions/65028943/google-or-tools-tsp-spanning-multiple-days-with-start-stop-times> with
> > a bounty.*
> >

> > I have been using Google OR-Tools to optimize routing of a single vehicle
> > over the span of a single day. I have included the code below, which runs
> > in Python 3.
> >
> > The time matrix I have included represents 42 locations; the first two
> > locations are the depot where the vehicle will begin and end the day (these
> > won't necessarily always be the same location). The remaining forty
> > locations all represent McDonald's restaurants in the Minneapolis area. The
> > vehicle cannot leave the depot until 6:00am (21600 seconds), and must
> > return to the depot by 6:00pm (64800 seconds). I do have time windows
> > enforced for visits to the locations, but for the sake of brevity and
> > simplicity in my question, I've allowed the locations to be visited at any
> > time (while still meeting the condition of beginning and ending the day at
> > 6:00am and 6:00pm, respectively). Additionally, every location must be
> > visited for a duration of 30 minutes (1800 seconds).
> >
> > When I run my implementation, there are (as you'd expect) many locations
> > that are not visited, due to all of the existing constraints. I want to
> > modify my solution to allow for schedules to be created across multiple
> > days. For example, I would like my implementation to explore solutions
> > where the locations are schedule to be visited the following day as well,
> > starting at 6:00am (21600 seconds + 86400 seconds) and ending at 6:00pm

> > (64800 seconds + 86400 seconds). I also want to allow for *disjointed
> > time windows
> > <https://github.com/google/or-tools/blob/master/examples/cpp/cvrp_disjoint_tw.cc>*,

> > though I'm afraid that may be too much to ask for someone to help me with
> > at once. I have attempted this on my own, but my efforts have been
> > fruitless and yielded only errors. I thought sharing my working solution
> > and my constraints would be a good place to start when asking for help, but
> > I'd be more than happy to provide any additional context and information I
> > may have omitted.
> >
> > I have already referenced the following resources:
> >

> > - Multiple time windows for vehicle routing problem instance #167
> > <https://github.com/google/or-tools/issues/167>
> > - VRP with Time Windows - More than 1 time window per location #456
> > <https://github.com/google/or-tools/issues/456>
> > - Multiple Time Windows per Location, and Vehicle Specialties &
> > Replenishment
> > <https://groups.google.com/g/or-tools-discuss/c/MBq1TcqSQTI?pli=1>
> > - Multiple time windows vrp [or-tools]
> > <https://stackoverflow.com/questions/61456895/multiple-time-windows-vrp-or-tools>

> >
> > Are there any blatant errors in my usage of OR Tools? I'm happy to answer
> > any questions. Any help will be very appreciate! Thank you!

> > *I have also posted this question on Stack Overflow
> > <https://stackoverflow.com/questions/65028943/google-or-tools-tsp-spanning-multiple-days-with-start-stop-times> with
> > a bounty.*
> >
> > *Source
> > <https://gist.github.com/joshykautz/04b458558935845cc1d5cb81797de862>:*

> > *Output
> > <https://gist.github.com/joshykautz/04b458558935845cc1d5cb81797de862>:*

> > {'Dropped': [5, 8, 9, 20, 21, 22, 25, 27, 28, 30, 31, 32, 33, 34, 35, 36,
> > 37, 38, 39, 40, 41], 'Scheduled': [[0, 21600, 21600], [14, 21964, 21982],
> > [15, 24235, 24253], [10, 26468, 26486], [12, 28494, 28512], [11, 30568,
> > 30586], [13, 32677, 32695], [23, 34869, 34887], [29, 37037, 37055], [24,
> > 39103, 39121], [7, 41413, 41431], [3, 43898, 43916], [2, 46266, 46284], [4,
> > 48674, 48692], [6, 51672, 51690], [17, 53921, 53939], [19, 56163, 56181],
> > [18, 58543, 58561], [26, 60553, 60571], [16, 62703, 62721], [1, 64800,
> > 64800]]}
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "or-tools-discuss" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to or-tools-discu...@googlegroups.com.
> > To view this discussion on the web visit
> > https://groups.google.com/d/msgid/or-tools-discuss/793d6be3-ffcd-41c0-920c-9e3fe2fe2c1dn%40googlegroups.com

> > <https://groups.google.com/d/msgid/or-tools-discuss/793d6be3-ffcd-41c0-920c-9e3fe2fe2c1dn%40googlegroups.com?utm_medium=email&utm_source=footer>
> > .
> >
>
> --

> This message (and any associated files) may contain confidential and/or
> privileged information. If you are not the intended recipient or authorized
> to receive this for the intended recipient, you must not use, copy,
> disclose or take any action based on this message or any information
> herein. If you have received this message in error, please advise the
> sender immediately by sending a reply e-mail and delete this message. Thank
> you for your cooperation.
>

> --
> You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAAp4U%2BBw%2B3xVKBSWDhOcPp5nO31E27C%2BbcaB_-G%3DD0wZ9X%3DcyA%40mail.gmail.com.

[Mizux Seiha]

https://stackoverflow.com/questions/65028943/google-or-tools-tsp-spanning-multiple-days-with-start-stop-times/

[Josh Kautz]

Thank you for the advice and help, both @James and @Mizux!

My most recent implementation is available on GitHub.

It currently does yields a solution, but one that is not quite satisfactory to what I'm trying to achieve - definitely in the right ballpark though!

When seeding sample data for a solution that spans only two day, I am representing the locations in the matrix as:

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

This is the pattern I intend to follow if I were to solve across a span of additional day.

Currently, in the output returns a solution, the vehicle ends the first day at location [end day 2] (4th location in the list), which is where I want the vehicle to end on the second day. Instead, I am trying to have the vehicle end the first day at location [end day 1] (2nd location in the list). You can see this in the output that I have included below:

solution found.  Objective value is  518947
Dropped
[7, 11, 38, 39, 42]
Scheduled
[0, 0, '6:0', '6:0']
[40, 1, '6:5', '6:5']
[36, 2, '7:9', '7:9']
[35, 3, '7:42', '7:42']
[16, 4, '8:22', '8:22']
[18, 5, '9:26', '9:26']
[28, 6, '10:3', '10:3']
[20, 7, '10:37', '10:37']
[19, 8, '11:14', '11:14']
[8, 9, '11:53', '11:53']
[27, 10, '12:36', '12:36']
[21, 11, '13:13', '13:13']
[37, 12, '13:52', '13:52']
[23, 13, '14:27', '14:27']
[22, 14, '15:33', '15:33']
[41, 15, '16:14', '16:14']
[43, 16, '16:50', '16:50']
[30, 17, '17:38', '17:38']
[3, 18, '18:14', '18:14']
[2, 19, '4:33', '4:44']
[5, 20, '4:55', '5:6']
[4, 21, '5:34', '5:45']
[6, 22, '6:0', '6:10']
[17, 23, '6:49', '7:0']
[12, 24, '7:26', '7:37']
[14, 25, '8:0', '8:11']
[15, 26, '8:35', '8:46']
[13, 27, '9:11', '9:22']
[9, 28, '9:34', '9:45']
[26, 29, '9:58', '10:9']
[10, 30, '10:37', '10:48']
[32, 31, '11:20', '11:30']
[31, 32, '11:59', '12:10']
[25, 33, '12:35', '12:46']
[24, 34, '13:11', '13:22']
[29, 35, '13:51', '14:1']
[34, 36, '14:25', '14:36']
[33, 37, '15:5', '15:16']
[1, 38, '15:49', '16:0']

I appreciate all the help that I have received so far, and am entirely prepared to make this solution as available as possible to others (like @Miguel) going into the future. Thank you for your time, patience, and problem solving! :)

[blind.line]

Just adding a note to this thread, my “final” implementation is on github here: https://github.com/jmarca/tsp_multiple_days

And I wrote up my approach in a post here https://activimetrics.com/blog/ortools/multiday_tsp/

Note that my implementation and writeup deviates a bit from the original question as I focused on the use of slack to reset the dimension. 

James

On Dec 1, 2020, at 13:37, 'Josh Kautz' via or-tools-discuss <or-tools...@googlegroups.com> wrote:

Thank you for the advice and help, both @James and @Mizux!

My most recent implementation is available on GitHub.

It currently does yields a solution, but one that is not quite satisfactory to what I'm trying to achieve - definitely in the right ballpark though!

...

[Josh Kautz]

Likewise, to follow up the thread, I'm happy to share the solution at which the community has helped me arrive.

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.