2d:null 2e:["$","title",null,{"children":"Vehicle Breakdown Contingency Planning to Reduce Delivery Failures | NB.AI Solutions Team | Observable"}] 33:T46a,# Approach 1. Use the MVRP API to assign jobs to vehicles prior to the start of the shift. 2. To simulate vehicle breakdowns, select a point along a vehicle's route and induce a failure at that step. 3. Run an isochrone for 15 minutes from the point of failure. Identify all vehicles that fall within that isochrone and, for each vehicle, follow these steps until all orders have been assigned: * Determine how many orders the vehicle can fulfill. If the vehicle had previously been filled to capacity from the depot but has made deliveries since, it may now have space for more items. * Run an MVRP from the point of failure for the selected vehicle, including any new orders that would potentially be assigned to it, as well as any items that remain to be completed. Ensure that the vehicle can successfully satisfy all of these orders and return to the depot before the end of the shift. * If the above conditions are met, assign the new orders to the vehicle. 4. Repeat step 3 for isochrones of 30 and 45 minutes, until there are no vehicles available within those ranges or until all orders have been reassigned.34:T75c,viewof inputs = { const objectives = [ { name: "Minimize Time", value: "duration" }, { name: "Minimize Distance", value: "distance" } ]; let shiftStart = new Date(); shiftStart.setDate(new Date().getDate() + 1); shiftStart.setHours(5); shiftStart.setMinutes(45); shiftStart.setSeconds(0); shiftStart.setMilliseconds(0); shiftStart.toLocaleDateString(); return guard(({ template }) => Inputs.form( { vehicleCapacity: Inputs.select( [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 50, 100], { label: "Vehicle capacity", value: 6 } ), nVehicles: Inputs.select([5, 10, 15, 20, 25, 50], { label: "Number of vehicles", value: 15 }), nVehicles: Inputs.select([5, 10, 15, 20, 25, 50], { label: "Number of vehicles", value: 15 }), city: Inputs.select(cities, { label: "Select city", format: (x) => x.name, value: cities.find((t) => t.name === "Columbus") }), nOrders: Inputs.select( [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 500, 1000], { label: "Number of orders", value: 50 } ), objectiveFunction: Inputs.select(objectives, { label: "Objective Function", format: (x) => x.name, value: objectives.find((t) => t.name === "Minimize Time") }), shiftDuration: Inputs.select( Array.from(Array(20).keys()).map((k) => k * 0.5 + 0.5), { label: "Shift duration (in hours)", value: 5 } ), shiftStart: Inputs.datetime({ value: shiftStart.toISOString().slice(0, -1), label: "Shift start time" }) }, { template } ) ); }35:T452,{ apiKey; const container = html`

`; yield container; const centroid = city.centroid.split(","); const nbmap = createMap("test2", centroid, 10); nbmap.on("load", () => { const dataList = document.getElementById("data-list"); drawRoute(nbmap.map, "route", vehicleSelector.geometry, "#ea580c", 2.5); onlyJobs(vehicleSelector.steps).forEach((step) => { const time = dateFns.format(new Date(step.arrival * 1000), "h:mm"); const location = orders.get(step.id).description; const marker = drawOrder(nbmap.map, step.location, location); const stepElement = document.createElement("div"); stepElement.innerHTML = `

${time}:: ${location}

`; dataList.appendChild(stepElement); }); drawDepot(nbmap.map, centroid); }); }36:T541,{ apiKey; const dataListId = "data-list-3"; const mapId = "map-3"; const container = html`

`; yield container; const centroid = city.centroid.split(","); const nbmap = createMap(mapId, centroid, 10); nbmap.on("load", () => { const dataList = document.getElementById(dataListId); const route = initialRoutes.get(failedVehicle.id); if (route) { drawRoute(nbmap.map, "route", route.geometry, "#ea580c", 2.5); onlyJobs(route.steps).forEach((step) => { const time = dateFns.format(new Date(step.arrival * 1000), "h:mm"); const location = orders.get(step.id).description; const marker = drawOrder(nbmap.map, step.location, location); const done = afterFailure(step) ? "🚫" : "✅"; const stepElement = document.createElement("div"); stepElement.innerHTML = `

${done} ${time}:: ${location}

`; dataList.appendChild(stepElement); }); } drawDepot(nbmap.map, centroid); }); }37:T5dc,{ const container = html`

`; yield container; const centroid = city.centroid.split(","); const nbmap = createMap("isochrone-map", centroid, 8); nbmap.on("load", () => { let polygons = JSON.parse(JSON.stringify(isochrone)); isochrone.features.forEach((ft, idx) => { let isopoly = turf.lineToPolygon(ft.geometry); polygons.features[idx] = isopoly; }); if (!nbmap.map.getSource("isochrone")) { nbmap.map.addSource("isochrone", { type: "geojson", data: null }); } nbmap.map.getSource("isochrone").setData(polygons); nbmap.map.addLayer({ id: "isochrone", type: "fill", source: "isochrone", layout: {}, paint: { "fill-color": "rgba(150, 20, 10, 1)", "fill-opacity": 0.15 // "line-width": 3 } }); drawFailedVehicle( nbmap.map, failedVehicle.description, failureStep.location ); nextVehicleStepsMap.forEach((stepId, vehicleId) => { if (vehicleId !== failedVehicle.id) { const step = orders.get(stepId); const vehicle = vehicles.get(vehicleId); const nStepsRemaining = onlyJobs( initialRoutes.get(vehicleId).steps ).filter(afterFailure).length; const description = `${vehicle.description} (${nStepsRemaining} jobs left)`; drawVehicle(nbmap.map, description, step.location); } }); }); }38:T42b,{ const result = [...reassignResult.routes.entries()].map( ([vehicleId, [route]]) => { const initialSteps = onlyJobs(initialRoutes.get(vehicleId).steps); const nNewJobs = reassignResult.newOrders.get(vehicleId).length; const finalStep = route.steps.at(-1); const previousStep = initialSteps.filter(beforeFailure)[0]; const previousStepDuration = previousStep === undefined ? 0 : previousStep.duration / 60; return { "Vehicle Name": vehicles.get(vehicleId).description, "Jobs (original)": initialSteps.length, "Jobs completed": initialSteps.filter(beforeFailure).length, "Jobs (reassigned)": nNewJobs, "Jobs (updated)": nNewJobs + initialSteps.filter(afterFailure).length, "Travel time (original)": Math.round( initialRoutes.get(vehicleId).steps.at(-1).duration / 60 ), "Travel time (updated)": Math.round( finalStep.duration / 60 + previousStepDuration ) }; } ); if (result.length > 0) return table(result); }39:T99b,reassignResult = { let newOrders = new Map(); let routes = new Map(); let geometries = new Map(); let unassignedOrderIds = onlyJobs(initialRoutes.get(failedVehicle.id).steps) .filter(afterFailure) .map((step) => step.id); let isochroneIdx = 0; while (unassignedOrderIds.length > 0 && isochroneIdx < 3) { const sortedVehicleIds = vehiclesInIsochrones[isochroneIdx] .map((vehicleId) => [ vehicleId, turf.distance( turf.point(failureStep.location), turf.point(orders.get(nextVehicleStepsMap.get(vehicleId)).location) ) ]) .sort((a, b) => a[1] - b[1]) .map(([vehicleId]) => vehicleId); for (let vehicleId of sortedVehicleIds) { const vehicle = vehicles.get(vehicleId); const remainingSteps = onlyJobs(initialRoutes.get(vehicleId).steps) .filter(afterFailure) .map((step) => step.id); const nAssignable = Math.min( vehicleCapacity - remainingSteps.length, unassignedOrderIds.length ); if (nAssignable > 0) { const mvrpInput = processMVRPInputs( // Vehicles [ createVehicle( vehicleId, vehicle.description, [failureStep.arrival, vehicle.time_window[1]], // TODO change this failureStep.location, finalStepMap.get(vehicleId).location ) ], // Jobs [ // nAssignable incomplete jobs from failed vehicle ...unassignedOrderIds.slice(0, nAssignable), // Remaining jobs from current vehicle ...remainingSteps ].map((stepId) => orders.get(stepId)), serviceTime, vehicleCapacity ); // Run MVRP to check if nAssignable orders can be assigned to the vehicle const res = await mvrp(mvrpInput); if (res.status === "Ok" && res.result.summary.unassigned === 0) { routes.set(vehicleId, res.result.routes); newOrders.set(vehicleId, unassignedOrderIds.slice(0, nAssignable)); const newGeometry = await getUpdatedGeometry( vehicleId, res.result.routes[0] ); geometries.set(vehicleId, newGeometry); unassignedOrderIds = unassignedOrderIds.slice(nAssignable); } } } isochroneIdx++; } return { unassignedOrderIds, newOrders, routes, geometries }; }3a:T65e,{ const container = html`

`; yield container; const centroid = city.centroid.split(","); const nbmap = createMap("reroutes-map", centroid, 12); const vehicleId = selectedNewRoute[0]; nbmap.on("load", () => { drawDepot(nbmap.map, centroid); drawFailedVehicle(nbmap.map, "Failed vehicle", failureStep.location); nbmap.map.addSource("route", { type: "geojson", data: { type: "Feature", properties: {}, geometry: { type: "LineString", coordinates: nextbillion.utils.polyline .decode(selectedNewRoute.at(1), 6) .map((c) => c.reverse()) } } }); const steps = [ // Orders delivered before a vehicle failed ...initialRoutes .get(vehicleId) .steps.filter(beforeFailure) .map((step) => step.location) .slice(1), // Ignore depot // Order that the vehicle was en route to delivering when a vehicle failed orders.get(nextVehicleStepsMap.get(vehicleId)).location, // Remaining orders ...reassignResult.routes .get(vehicleId) .at(0) .steps.map((step) => step.location) .slice(1, -1) // Ignore depot ]; steps.forEach((step) => { drawOrder(nbmap.map, step); }); nbmap.map.addLayer({ id: "route", type: "line", source: "route", layout: { "line-join": "round", "line-cap": "round" }, paint: { "line-color": "#ea580c", "line-width": 2.5 } }); }); }3b:T4b5,function getRoutesGeoJson(mvrpResult) { let routesGeoJson = { type: "FeatureCollection", features: [] }; // we create a geojson object to send to our mapview elements // It will be a feature collection of all the route polylines initialRoutes.forEach((rte, idx) => { let feature = { type: "Feature", properties: { id: rte.vehicle, vin: rte.description }, geometry: { coordinates: nextbillion.utils.polyline .decode(rte.geometry, 5) .map((c) => c.reverse()), type: "LineString" } }; routesGeoJson.features.push(feature); rte.steps.forEach((st, stIdx) => { let stop = { type: "Feature", properties: { id: rte.vehicle, vin: rte.description, description: st.description, stop_idx: stIdx, arrival: st.arrival, type: st.type, pointType: (st.type == "start") | (st.type == "end") ? 16 : 255 }, geometry: { coordinates: [st.location[1], st.location[0]], type: "Point" } }; routesGeoJson.features.push(stop); }); }); return routesGeoJson; }3c:T588,function processMVRPInputs(vehicles, jobs, serviceTime, vehicleCapacity) { let loc_index = 0; let location = ""; let vehicles_ = []; let jobs_ = []; { let jobs_index = 0; jobs.forEach((j) => { let job = { id: j.id, description: j.description, pickup: [1], location_index: loc_index++, service: serviceTime, location: j.location }; jobs_.push(job); if (jobs_index != 0 && jobs.length <= jobs.length) { location += "|"; } location += `${j.location[0]},${j.location[1]}`; jobs_index++; }); } { let vehicles_index = 0; vehicles.forEach((v, idx) => { if (vehicles_index < vehicles.length) { location += "|"; } location += `${v.startLocation[0]},${v.startLocation[1]}` + "|" + `${v.endLocation[0]},${v.endLocation[1]}`; let vehicle = { index: idx + 1, id: v.id, description: v.description, start_index: loc_index++, end_index: loc_index++, time_window: v.time_window, capacity: [vehicleCapacity], startLocation: v.startLocation, endLocation: v.endLocation }; vehicles_.push(vehicle); vehicles_index++; }); } const locations = { id: 1, location }; return { locations, jobs: jobs_, vehicles: vehicles_ }; }3d:T111d,table = (data, options) => { options = Object.assign({}, defaultOptions, options); const { sortable, rank, paged } = options; let sortKey = undefined; let sortDirection = true; let page = 0; if (sortable && rank) { throw new Error("A table can either be ranked or sortable, but not both"); } let columns = Object.keys(data[0]).map((key) => { const opts = options.columns[key] || {}; return { key: key, type: opts.type || typeof data[0][key], options: opts }; }); function bake() { if (sortKey) { data = data.slice().sort((a, b) => { let as = a[sortKey]; let bs = b[sortKey]; // make this sort stable if (as == bs) return JSON.stringify(a).localeCompare(JSON.stringify(b)); let res = as > bs ? 1 : as < bs ? -1 : 0; if (sortDirection) res = -res; return res; }); } let offset = page * paged; let rows = data.slice(offset, offset + (paged || data.length)); let pages = paged ? Math.ceil(data.length / paged) : 1; return html`

${ options.header === false ? `` : html` ${rank ? html`` : ""} ${columns.map((c) => { return th(c, sortKey, sortDirection, sortable); })} ` } ${rows.map( (row, i) => html` ${rank ? html`` : ""} ${columns.map((c) => { let displayValue = (c.options.formatter || identity)( row[c.key], i, row ); if ( displayValue instanceof window.HTMLElement && displayValue.tagName == "TD" ) { return displayValue; } return html``; })} ` )}


${offset + i + 1}	${displayValue}

${ pages > 1 ? html`` : "" }

`; } let dom = bake(); function rerender() { dom.firstChild.remove(); dom.appendChild(bake().firstChild); } dom.addEventListener("click", (e) => { if (e.target.tagName === "TH" && sortable) { if (sortKey == e.target.dataset.key) { sortDirection = !sortDirection; } sortKey = e.target.dataset.key; rerender(); } if (e.target.tagName === "BUTTON") { if (e.target.dataset.action) { switch (e.target.dataset.action) { case "next": page++, rerender(); break; case "previous": page--, rerender(); break; } } else if (e.target.dataset.page) { (page = parseInt(e.target.dataset.page)), rerender(); } } }); return dom; }3e:T57a,function guard(fn, options = {}) { const { submitLabel = "Submit", resetLabel = "Reset", required = false, resubmit = true, width = "fit-content", justify = "start" } = options; const onSubmit = () => { value = input.value; submit.disabled = !resubmit; reset.disabled = true; wrapper.dispatchEvent(new Event("input", { bubbles: true })); }; const onReset = () => { input.value = value; submit.disabled = !resubmit; reset.disabled = true; }; const submit = htl.html`

\n Undelivered orders in failed vehicle\n	\n ${nUndeliveredOrdersInFailedVehicle}\n
\n Reassigned orders\n	\n ${nReassignedOrders}\n
\n Impact of vehicle failure reduced by\n	\n ${(nUndeliveredOrdersInFailedVehicle / nReassignedOrders) * 100}%\n