31:T1ad0,**Background** The **Vehicle Routing Problem** (VRP) is an example of a computationally challenging problem in mathematical optimisation which has significant impact on the logistics and supply chain industry. It is an extension of the more commonly known **Travelling Salesman Problem** (TSP) where a vehicle departs a starting location (usually a depot) and is supposed to visit each stop once and only once along the route before returning to the start. The solution to the TSP is given by the route that minimises the distance travelled across the whole route. Similarly, the Vehicle Routing Problem describes a fleet of vehicles starting at a depot and visiting each delivery location once and only once between them. Each vehicle has its own route over a subset of the delivery locations and the optimal solution is the one that minimises distance travelled across the whole fleet. The VRP optimisation problem becomes two distinct problems rolled into one: - what is the optimal subset of locations that should be allocated to each vehicle - what is the optimal sequence of delivery locations for each vehicle to visit The **schedule** solution describes both the allocation of delivery locations to each vehicle and the sequence in which the vehicle should visit those locations before returning to the depot. **Why is this so difficult?** The sheer number of possible permutations of vehicles visiting a particular subset of delivery locations in a given sequence is absolutely mind-blowing! A single van route with 61 deliveries has more possible schedule solutions than the **number of atoms in the visible universe** (5.1 × 10⁸³ solutions as compared to approximately 1.0 × 10⁸¹ atoms). If instead you allow 10 vans to visit the same 61 locations in a fleet operation, you increase the number of possible solutions by 90,000,000,000 times again — a total of 4.6 × 10⁹⁴ solutions. Clearly generating and checking all these solutions is out of the question, and this is where mathematical optimisation and AI come in; they provide algorithms to reduce the explored search space dramatically and home in on the best solution or a very good candidate solution, in a reasonable time. **Variations and Industry Extensions** There are many variations to the Vehicle Routing Problem that reflect the challenges and extra constraints presented by the logistics and supply-chain industry and many of the clients we work with. The exact set of extensions varies depending on the company and also whether they are servicing a backbone heavy fleet network (suppliers to depots and depots to depots) or a final-mile solution (depots to customers). - **maximum capacity vehicles**: vehicles are typically constrained in the volume and weight of the goods they can carry - **temperature zones**: some industries, particularly in pharmaceutical and grocery supply chain, require one or more of ambient, chilled or frozen compartments for their goods. Specially equipped vehicles can support this flexibly through moveable bulkheads which separate the different zones on the vehicle. - **arrival-time windows**: many networks have pre-agreed arrival windows for the vehicles to reach their delivery locations. Sometimes breaching these windows can result in a service penalty. - **loading and unloading time**: loading and unloading goods at a depot or at a delivery point takes time which has to be factored into a schedule. This can be impacted by both the amount of goods being loaded/unloaded and the geographical layout of the delivery area or location of the delivery point, e.g. delivery to an inner-city store with a constrained loading bay or a customer in a high-rise flat. - **heterogeneous fleet**: many fleet operators have different types of vehicle with different capacities, weight limits and operating requirements, e.g. small fleet for inner city delivery and heavy fleet for inter-city transportation - **location constraints**: where there are multiple vehicle types in a fleet, there will often be constraints on which vehicle type can visit a given delivery location, e.g. an articulated lorry may not be able to visit a site with a space-limited loading area - **driving breaks, meal breaks** and **maximum driving time**: by law in many countries, delivery drivers have to have mandated breaks after a certain number of hours on the road. Many companies will often have designated rest locations which can be factored into the schedule. There is often also a specified maximum number of hours a driver can drive in a day, a week and a 2 week period in aggregate. - **rush hour and busy periods**: rush-hour routes can take much longer to travel than the same route at off-peak times of day. - **multiple depots**: usually vehicles are allocated to a single depot at which they load and finish their route. In some networks, vehicles can end their route at another depot or replenish mid-route at an interim depot. - **cross-docking**: in backbone networks, lorries can perform a cross-docking manoeuvre at a depot where their contents are unloaded, sorted, grouped and redistributed to a new set of vehicles for more efficient onward delivery. The optimal selection of these cross-dock locations is an optimisation problem in itself. - **EV charging**: EV fleets that require charging will usually do so at the depot overnight but schedules can be generated which cater for en-route charging at optimal locations. Account needs to be taken of the battery capacity, miles covered and even operating temperature. - **multi-modal delivery**: in postal networks and some delivery-partner industries, items can be delivered on foot, by bike or by van or sometimes several of these. The selection of transport mode and the location where that should optimally happen adds to the complexity of the problem. **Objective** Not all industrial vehicle routing problems seek to minimise distance. Some industries have a cost base that is dominated more by the number of hours driven or the number of vehicles used. It is quite usual to have an objective (technically, an *objective function*) that combines elements of all three: distance, hours and number of routes. In some scenarios and in particular if undertaking strategic optimisation over a longer period of time, an element of asset cost and maintenance for the fleet can also be factored in. **Example Setup** In the map of London below, the **Depot** is represented by a black square and the **29 delivery locations** are denoted by the red squares. All vans start and return to the depot. Each location requires delivery of one parcel and the vans can take a designated number of parcels per vehicle. **Objective**: To deliver a parcel to each location while minimising the distance travelled across the network.32:T4fe,## Flexing constraints Let's now examine a larger example to demonstrate the impact of flexing two constraints simultaneously. In this instance, we consider - **arrival-time window**: goods need to be served during a time interval specified by the store to ensure it can process the delivery - **maximum vehicle capacity**: the single vehicle type used to serve the network has a limited capacity, and therefore can visit only a certain amount of stores in each route before returning to depot to reload

In the visualisation below we have a total of 178 stores plus one depot (denoted by the black square as before). Each store has initially assigned a two-hour time window between 5am and 2pm to be served. Additionally, each route is constrained to at most 9 stops due to the vehicle capacity limit. Routes are highlighted by painting travelled legs using dashed lines of the same colour. Note that planned routes by the solver do not seem optimal at first sight: we have crossings between travelled legs, and some stores seem to be visited in odd order. This is due to the fact that different time window constraints apply at each store, and our solution ensures that the total time used in serving the schedule is as small as possible.

33:T6fb,chart_attractor1 = { // const xScaleDist = d3.scaleLinear() // .domain([1, 10]) // .range([config.left_margin_plot, 10*config.frame_x + config.left_margin_plot]); const svg = d3.create("svg") .attr("viewBox", [0, 0, surface.width, surface.height]) .style("display", "block") .style("margin", 0) .style("width", surface.width) .style("height", surface.height); svg.append("g") .attr("stroke", "#fff") .attr("stroke-opacity", 1) .selectAll("path") .data(contours(grid_attractor)) .join("path") .attr("fill", d => color_palette.color_gauss(d.value)) .attr("opacity", 1) .attr("d", d3.geoPath()); const x_position = (number_stops - 9) * grid_attractor.k - config.node_size const x_offset = (number_stops == 9) * config.node_size - (number_stops == 14) * config.node_size const y_position = (hour_window / 2 - 1) * grid_attractor.k - config.node_size const y_offset = (hour_window == 2) * config.node_size - (hour_window == 10) * config.node_size svg.append('rect') .attr('x', x_position + x_offset) .attr('y', y_position + y_offset) .attr('height', 2 * config.node_size) .attr('width', 2 * config.node_size) .attr('fill', "#FF0000") .attr('stroke', 'black') svg.append('rect') .attr('x', 1000) .attr('y', y_position + y_offset) .attr('height', 2 * config.node_size) .attr('width', 2 * config.node_size) .attr('fill', "#FF0000") .attr('stroke', 'black') // let axisContainerX = svg.append('g').call(plotAxis.xAxisDistance) // let axisContainerY = svg.append('g').call(plotAxis.yAxisDistance) // axisContainerX.call(axisTransform) // axisContainerY.call(axisTransform) // Add bound rectangle bound_rectangle(svg) return svg.node(); }34:T412,

In the display above we can see the cost of serving the schedule (darker green for larger costs, lighter green for lower costs) as we vary both the time window and the maximum number of stops. Serving cost is calculated as a weighted sum of total distance covered (in kilometers) and driver-hours required to serve all routes. In principle, this cost should always decrease as we relax the constraints. In this instance, we observe that the lowest cost is obtained when we specify a time window of 10h and allow a maximum of 12-14 stops.

Another interesting insight from these results is that, in general, the number of stops does not affect the optimal as much as it does flexing the time window. In particular, for a two-hour time window, expanding the vehicle capacity from 9 to 14 stops seems to give us virtually the same result. This is because with such restrictive constraint it will be very difficult to build any route that surpasses the nine-stop mark.

35:T5e6,## What do we learn

Mathematical optimisation and AI-based heuristics can dramtically change the structure of solution and savings associated with large vehicle routing problems. Potentially hundreds of depots with thousands of orders a day can be optimised in this way and the cost and environmental benefits can be huge.

We often see: - upwards of 10% of cost can be driven out of existing networks even when current industrial scheduling tools are being used - in situations where there is flexibility on the ground in arrival time, or delivery day of the week across sets of locations, we have seen savings of 20% or more - further efficiencies can be gained by aligning the optimisation activity closer to the real time operation, e.g. optimising a schedule on a daily basis against known delivery demand (tactical) versus optimising a typical seasonal schedule against usual demand patterns (strategic).

The routes for these visualisations have been built using Datasparq's (https://www.datasparq.ai/) vehicle routing optimiser. We use a combination of metaheuristics and large-scale computing. Our solver can tackle routing problems with deliveries in the order of thousands, and is able to compete with state-of-the-art specialised commercial software. Please get in touch if you'd like to find out more about our routing solutions and use cases, and how we can help your business unlock savings through efficient scheduling. 36:T5c0,class PlotVariables { constructor(){ //=================================================================== // Scale //=================================================================== PlotVariables.xScaleDist = d3.scaleLinear() .domain([1, config.max_x_axis]) .range([config.left_margin_plot, 10*config.frame_x + config.left_margin_plot]); PlotVariables.distanceScale = d3.scaleLinear() .domain([0, config.max_y_axis]) .range([config.top_margin + 10*config.frame_y, config.top_margin]); } //=================================================================== // Axis //=================================================================== xAxisDistance(g) { g.attr('transform', `translate(${0*config.left_margin_plot},${10*config.frame_y + config.top_margin})`) .call(d3.axisBottom(PlotVariables.xScaleDist).ticks(config.max_x_axis)) // Add label .append('text') .attr('class', 'axis-label') .attr('x', 5*config.frame_x) .attr('y', -300) // Relative to the y axis. .text('x axis label'); } yAxisDistance(g) { g.attr('transform', `translate(${0*config.frame_x + config.left_margin_plot},${0*config.top_margin})`) .call(d3.axisLeft(PlotVariables.distanceScale)) // Add label .append('text') .attr('class', 'axis-label') .text('Hola') .attr('transform', 'rotate(-90)') .attr('x', -10) .attr('y', -60); // Relative to the y axis. } }37:T5bc,class PlotAxis { constructor(){ //=================================================================== // Scale //=================================================================== PlotVariables.xScaleDist = d3.scaleLinear() .domain([1, config.max_x_axis]) .range([config.left_margin_plot, 10*config.frame_x + config.left_margin_plot]); PlotVariables.distanceScale = d3.scaleLinear() .domain([0, config.max_y_axis]) .range([config.top_margin + 10*config.frame_y, config.top_margin]); } //=================================================================== // Axis //=================================================================== xAxisDistance(g) { g.attr('transform', `translate(${-config.left_margin_plot},${10*config.frame_y + 7.5*config.top_margin})`) .call(d3.axisBottom(PlotVariables.xScaleDist).ticks(config.max_x_axis)) // Add label .append('text') .attr('class', 'axis-label') .attr('x', 0*5*config.frame_x) .attr('y', 0) // Relative to the y axis. .text('x axis label'); } yAxisDistance(g) { g.attr('transform', `translate(${0*config.frame_x + config.left_margin_plot},${0*config.top_margin})`) .call(d3.axisLeft(PlotVariables.distanceScale)) // Add label .append('text') .attr('class', 'axis-label') .text('Hola') .attr('transform', 'rotate(-90)') .attr('x', -10) .attr('y', -60); // Relative to the y axis. } }38:T6b4,function add_link(svg, locations, connection, colour, config) { const node1 = locations[connection[0]]; const node2 = locations[connection[1]]; const linkSource = { x: node1[0]*config.scale_factor_routes + config.left_margin, y: node1[1]*config.scale_factor_routes + config.top_margin}; // Choose top or bottom link const linkTarget = { x: node2[0]*config.scale_factor_routes + config.left_margin, y: node2[1]*config.scale_factor_routes + config.top_margin}; const link = d3 .linkHorizontal() .x(d => d.x) .y(d => d.y)({ source: linkSource, target: linkTarget }); svg .append('path') .attr('class', 'link') .attr('d', link) .attr('stroke-width', config.stroke_width * 0.8) .attr('stroke', colour) .style("stroke-dasharray", ("3, 3")) .attr('opacity', 1) .attr('fill', 'none') .on("mouseover", function(){ d3.select(this) //.attr("stroke", "#000000") .attr('stroke-width', config.stroke_width * 0.3) }) .on("mouseout", function(){ d3.select(this) .attr("stroke", colour) }); // svg // .append('line') // .attr('class', 'link') // .attr('x1', linkSource.x) // .attr('y1', linkSource.y) // .attr('x2', linkTarget.x) // .attr('y2', linkTarget.y) // .attr('stroke-width', config.stroke_width) // .attr('stroke', colour) // .attr('opacity', 1) // .attr('fill', 'none') // .on("mouseover", function(){ // d3.select(this) // .attr("stroke", "#000000") // }) // .on("mouseout", function(){ // d3.select(this) // .attr("stroke", colour) // }); }39:T7e3,connection_steps = [ // Connections step 0 [[0, 1], [1, 2], [2, 3], [3, 5], [5, 0], [0, 4], [4, 12], [12, 13], [13, 10], [10, 8], [8, 0], [0, 7], [7, 9], [9, 6], [6, 11], [11, 0]], // Connections step 1 [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 0], [0, 12], [12, 13], [13, 10], [10, 8], [8, 0], [0, 7], [7, 9], [9, 6], [6, 11], [11, 0]], // Connections step 2 [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0], [0, 5], [5, 12], [12, 13], [13, 10], [10, 8], [8, 0], [0, 7], [7, 9], [9, 6], [6, 11], [11, 0]], // Connections step 3 [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0], [0, 5], [5, 12], [12, 13], [13, 10], [10, 0], [0, 7], [7, 9], [9, 8], [8, 6], [6, 11], [11, 0]], // Connections step 4 [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0], [0, 5], [5, 12], [12, 11], [11, 13], [13, 10], [10, 0], [0, 7], [7, 9], [9, 8], [8, 6], [6, 0]], // Connections step 5 [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0], [0, 5], [5, 12], [12, 11], [11, 13], [13, 0], [0, 7], [7, 9], [9, 8], [8, 10], [10, 6], [6, 0]], // Connections step 5 [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0], [0, 5], [5, 12], [12, 11], [11, 13], [13, 6], [6, 0], [0, 7], [7, 9], [9, 8], [8, 10], [10, 0]], // Connections step 6 [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0], [0, 5], [5, 12], [12, 11], [11, 13], [13, 6], [6, 0], [0, 7], [7, 8], [8, 10], [10, 9], [9, 0]] ] 3a:Tdca,class DataConnectionsLarge { constructor(){ // 2-HOUR TIME WINDOW this.data_connections1 = getDataLarge('data_connections_hours_2_stops_9') this.data_connections2 = getDataLarge('data_connections_hours_2_stops_10') this.data_connections3 = getDataLarge('data_connections_hours_2_stops_11') this.data_connections4 = getDataLarge('data_connections_hours_2_stops_12') this.data_connections5 = getDataLarge('data_connections_hours_2_stops_13') this.data_connections6 = getDataLarge('data_connections_hours_2_stops_14') // 4-HOUR TIME WINDOW this.data_connections7 = getDataLarge('data_connections_hours_4_stops_9') this.data_connections8 = getDataLarge('data_connections_hours_4_stops_10') this.data_connections9 = getDataLarge('data_connections_hours_4_stops_11') this.data_connections10 = getDataLarge('data_connections_hours_4_stops_12') this.data_connections11 = getDataLarge('data_connections_hours_4_stops_13') this.data_connections12 = getDataLarge('data_connections_hours_4_stops_14') // 6-HOUR TIME WINDOW this.data_connections13 = getDataLarge('data_connections_hours_6_stops_9') this.data_connections14 = getDataLarge('data_connections_hours_6_stops_10') this.data_connections15 = getDataLarge('data_connections_hours_6_stops_11') this.data_connections16 = getDataLarge('data_connections_hours_6_stops_12') this.data_connections17 = getDataLarge('data_connections_hours_6_stops_13') this.data_connections18 = getDataLarge('data_connections_hours_6_stops_14') // 8-HOUR TIME WINDOW this.data_connections19 = getDataLarge('data_connections_hours_8_stops_9') this.data_connections20 = getDataLarge('data_connections_hours_8_stops_10') this.data_connections21 = getDataLarge('data_connections_hours_8_stops_11') this.data_connections22 = getDataLarge('data_connections_hours_8_stops_12') this.data_connections23 = getDataLarge('data_connections_hours_8_stops_13') this.data_connections24 = getDataLarge('data_connections_hours_8_stops_14') // 10-HOUR TIME WINDOW this.data_connections25 = getDataLarge('data_connections_hours_10_stops_9') this.data_connections26 = getDataLarge('data_connections_hours_10_stops_10') this.data_connections27 = getDataLarge('data_connections_hours_10_stops_11') this.data_connections28 = getDataLarge('data_connections_hours_10_stops_12') this.data_connections29 = getDataLarge('data_connections_hours_10_stops_13') this.data_connections30 = getDataLarge('data_connections_hours_10_stops_14') this.data_connections = [this.data_connections1, this.data_connections2, this.data_connections3, this.data_connections4, this.data_connections5, this.data_connections6, this.data_connections7, this.data_connections8, this.data_connections9, this.data_connections10, this.data_connections11, this.data_connections12, this.data_connections13, this.data_connections14, this.data_connections15, this.data_connections16, this.data_connections17, this.data_connections18, this.data_connections19, this.data_connections20, this.data_connections21, this.data_connections22, this.data_connections23, this.data_connections24, this.data_connections25, this.data_connections26, this.data_connections27, this.data_connections28, this.data_connections29, this.data_connections30, ] } }3b:Taad,svg_distance = { console.log("render svg distance") const svg = d3.select(DOM.svg(config.scale_factor*config.frame_x + config.left_margin_plot + config.right_margin, 10*config.frame_y + config.top_margin + config.bottom_margin)) svg.attr("class", "viz") // const width_margin = frame.width_revenue-frame.margin_revenue.left-frame.margin_revenue.right // Draw the x and y axes. let axisContainerX = svg.append('g').call(plotVar.xAxisDistance) let axisContainerY = svg.append('g').call(plotVar.yAxisDistance) axisContainerX.call(axisTransform) axisContainerY.call(axisTransform) // Labels svg .append('text') .attr('class', 'axis-label') .text('Max. capacity') .attr('x', config.left_margin_plot + 10*0.4*config.frame_x) .attr('y', config.top_margin + 10*config.frame_y + 1.2*config.frame_y); // Labels svg .append('text') .attr('class', 'axis-label') .text('Total Distance') .attr('x', -5*config.frame_x) .attr('y', 3.4*config.frame_y) .attr("transform", "rotate(-90)") // Plots svg .append('circle') .attr('cx', config.left_margin_plot + 10/6*(capacity-1)*config.frame_x) .attr('cy', config.top_margin + 10*config.frame_y - distance/config.max_y_axis*10*config.frame_y) .attr('r', 5) .attr('stroke', 'black') .attr('fill', 'steelblue') .attr('fill-opacity', .8) svg.line = svg.append("path") .datum(data_distance) //.style("stroke-dasharray", "6,6") .attr("fill", "none") .attr("stroke", "red") .attr("stroke-width", 2.5) .attr("stroke-linejoin", "round") .attr("stroke-linecap", "round") svg.line_horizontal = svg.append("path") .datum(data_distance) .style("stroke-dasharray", "3,3") .attr("fill", "none") .attr("stroke", "steelblue") .attr("stroke-width", 1.5) .attr("stroke-linejoin", "round") .attr("stroke-linecap", "round") svg.line_border_h = svg.append("path") .datum(data_distance) .attr("stroke", "black") .attr("stroke-width", .5) .attr("stroke-linejoin", "round") .attr("stroke-linecap", "round") svg.line_border_v = svg.append("path") .datum(distance_vector_border_v) .attr("stroke", "black") .attr("stroke-width", .5) .attr("stroke-linejoin", "round") .attr("stroke-linecap", "round") svg.line_vertical = svg.append("path") .datum(distance_vector_vertical) .style("stroke-dasharray", "3,3") .attr("fill", "none") .attr("stroke", "steelblue") .attr("stroke-width", 1.5) .attr("stroke-linejoin", "round") .attr("stroke-linecap", "round") // // Legend // // plotVar.legend(svg) return svg }3c:T4dc,svg_status_multipath = { const svg = d3.select(DOM.svg(config.total_frame_x, config.total_frame_y)); const connections = data_connections const locations = data_locations // Background //svg.style('background-image', 'url("https://images.fineartamerica.com/images-medium-large-5/3-london-england-street-map-michael-tompsett.jpg")') svg.style('background-image', 'url("https://play-ml.datasparq.ai/api/data/vehicle-routing/central_london.jpg")') svg.style('background-size', '100% 100%') background_rectangle(svg, config); // Connections for (var i = 0; i < connections.length; i++) { for (var j = 0; j < connections[i].length; j++){ if (j > 0) { point(svg, locations[connections[i][j][0]], config.colours.path[i], config); } // Add links add_link(svg, locations, connections[i][j], config.colours.path[i], config); } } svg.on("mouseover", function(){ d3.selectAll('path.link') .style('opacity', 0) }) .on("mouseout", function(){ d3.selectAll('path.link') .style('opacity', 1) }); // point(svg, locations[0], '#000000', config) // Points //for (var i = 0; i < locations.length; i++) { // point(svg, locations[i]); //} return svg }3d:T480,svg_large = { const svg = d3.select(DOM.svg(config_large.total_frame_x, config_large.total_frame_y)); // Background const connections = data_connections_large const locations = data_locations_large svg.style('background-image', 'url("https://play-ml.datasparq.ai/api/data/vehicle-routing/central_london.jpg")') svg.style('background-size', '100% 100%') background_rectangle(svg, config_large); // Connections for (var i = 0; i < connections.length; i++) { for (var j = 0; j < connections[i].length; j++){ if (j > 0) { point(svg, locations[connections[i][j][0]], config.colours.path[i], config_large); } // Add links add_link(svg, locations, connections[i][j], config.colours.path[i], config_large); } } svg.on("mouseover", function(){ d3.selectAll('path.link') .attr('stroke-width', config_large.stroke_width * 0.3) .style('opacity', 0) }) .on("mouseout", function(){ d3.selectAll('path.link') .attr('stroke-width', config_large.stroke_width * 0.8) .style('opacity', 1) }); // point(svg, locations[0], '#000000', config_large) return svg }3e:T7eb,class Config { constructor(scale_factor = 20, scale_factor_routes = 20, top_margin = 30, bottom_margin = 50, left_margin = 50, right_margin = 5, frame_x = 44, frame_y = 33, node_size = 10, bg3 = '#FFFFFFAA' // 121d3d88 ){ this.scale_factor = scale_factor this.scale_factor_routes = scale_factor_routes this.top_margin = top_margin this.bottom_margin = bottom_margin this.left_margin = left_margin this.right_margin = right_margin this.frame_x = frame_x this.frame_y = frame_y this.node_size = node_size // Frame size this.total_frame_x = this.frame_x*this.scale_factor + this.left_margin + this.right_margin this.total_frame_y = this.frame_y*this.scale_factor + this.top_margin + this.bottom_margin // Max y axis this.max_y_axis = 350 this.max_x_axis = 7 this.left_margin_plot = 200 this.right_margin_plot = 100 // stroke width this.stroke_width = 3 // Colour palette this.colours = {bg1: '#595f77aa', bg2: '#121d3d44', bg3: bg3, node: '#ff8774', link: '#ff877488'} this.colours.path = ["#0555F9", "#3DF110", "#6790EF", "#F46D43", "#AB181D", "#78C679", "#172CAD", "#A6CEE3", "#FD8D3C", "#A6D854", "#74791A", "#6A51A3", "#7FD000", "#1919F9", "#4F173C", "#A0A0F0", "#F010F0", "#375AE5", "#00FC30", "#F16913", "#6FE7FB", "#8C6BB1", "#41E984", "#762A83", "#FC9272", "#AE017E", "#2742F7", "#DF65B0", "#EF3B2C", "#74C476", "#23F567", "#8912A4", "#8ABE12", "#33FCD3", "#D5A4B1", "#899D43", "#AE6410", "#11E334", "#9009AF", "#EE32A1", "#B13145", "#2333B1", "#F0E117", "#5667E9", "#AE0012", ] } }3f:[] 2f:{"title":"Vehicle Routing Problem v2","cells":[{"id":0,"value":"# Vehicle Routing Problem v2\n\nPLEASE DO NOT COPY THIS MATERIAL WITHOUT PERMISSION FROM DATASPARQ. Please contact Kiko Rullan at kiko.rullan@datasparq.ai.","pinned":false,"hidden":false,"mode":"md"},{"id":1937,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":1102,"value":"svg_status_v2(data_locations)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1942,"value":"

\nInitially, in the route diagram below, all vans are set to carry only one parcel at a time and therefore the schedule requires 29 routes to serve the delivery locations. This is clearly very inefficient, requiring either a large fleet or many out-and-back routes in a duty by some vans. If the capacity of the vans is increased, this impacts both the efficiency of the driven routes and size of fleet and number of routes required.\n

","pinned":false,"hidden":false,"mode":"md"},{"id":1581,"value":"// svg_status_multipath(data_locations, data_connections[capacity-1])\n\n// dc.data_connections[capacity-1].then(data => {\n// return svg_status_multipath(data_locations, data)\n// })\nsvg_status_multipath.node()","pinned":false,"hidden":false,"mode":"ojs"},{"id":573,"value":"viewof capacity = slider({min: 1, \n max: 7,\n value: 1,\n step: 1,\n description: 'max capacity'})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1960,"value":"

\n**You can use the slider** to allow a van to transport a maximum of *m* parcels at a time. Depending on this capacity, the total travelled miles required to cover all deliveries varies significantly. For each capacity scenario, we optimise the routes to minimise the total travelled distance in each schedule. This variation is shown below, as we move the slider that specifies the maximum capacity, we observe how the number of routes and schedule changes.\n

","pinned":false,"hidden":false,"mode":"md"},{"id":626,"value":"svg_distance.node()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1948,"value":"The total distance covered by the delivery vans is shown in the graph above. As we increase the capacity of the vans, we observe a consistent decrease in the required miles to cover all deliveries. We also see the number of routes drop from 29 to 5; a significant decrease in fleet cost and driver time potentially.","pinned":false,"hidden":false,"mode":"md"},{"id":1072,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1950,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":1349,"value":"// dcl.data_connections[(hour_window-2)/2].then(data => {\n// return routes_multipath(data_locations_large, data)\n// })\n\n// dcl.data_connections[(hour_window-2)/2].then(data => {\n// return svg_large.node()\n// })\nsvg_large.node()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1511,"value":"viewof hour_window = slider({min: 2, \n max: 10,\n value: 2,\n step: 2,\n description: 'time window'})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1856,"value":"viewof number_stops = slider({min: 9, \n max: 14,\n value: 9,\n step: 1,\n description: 'max stops'})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1968,"value":"

\n**You can use the sliders above** to explore different routing solutions when we use time windows of {2, 4, 6, 8, 10} hours and allow a maximum of {9, 10, 11, 12, 13, 14} per route. As we loosen both constraints, we find routing solutions that require less vehicles/personnel and cover a smaller total distance. \n

\n\n### Cost of serving the schedule","pinned":false,"hidden":false,"mode":"md"},{"id":1718,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":1973,"value":"$34","pinned":false,"hidden":false,"mode":"md"},{"id":1975,"value":"$35","pinned":false,"hidden":false,"mode":"md"},{"id":1316,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1763,"value":"function bound_rectangle(svg){\n svg.append(\"rect\")\n \t.attr(\"x\", 0)\n \t.attr(\"y\", 0)\n \t.attr(\"height\", surface.height)\n \t.attr(\"width\", surface.width)\n \t.style(\"stroke\", '#666')\n \t.style(\"fill\", \"none\")\n \t.style(\"stroke-width\", 2) \n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1724,"value":"contours = (grid) => {\n return d3.contours().size([grid.n, grid.m]).thresholds(surface.thresholds)(grid).map(transform)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1726,"value":"// Converts from grid coordinates (indexes) to screen coordinates (pixels).\ntransform = ({type, value, coordinates}) => {\n return {type, value, coordinates: coordinates.map(rings => {\n return rings.map(points => {\n return points.map(([x, y]) => ([\n grid_attractor.x + grid_attractor.k * x,\n grid_attractor.y + grid_attractor.k * y\n ]));\n });\n })};\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1731,"value":"grid_attractor = {\n const q = surface.q; // The level of detail, e.g., sample every 4 pixels in x and y.\n const x0 = 0, x1 = surface.width;\n const y0 = 0, y1 = surface.height;\n const n = Math.ceil((x1 - x0) / q) + 1;\n const m = Math.ceil((y1 - y0) / q) + 1;\n const grid = cost_vector;//new Array(n * m);\n // for (let j = 0; j < m; ++j) {\n // for (let i = 0; i < n; ++i) {\n // grid[j * n + i] = Math.sqrt(j * i);\n // }\n // }\n grid.x = -q/2;\n grid.y = -q/2;\n grid.k = q;\n grid.n = n;\n grid.m = m;\n return grid;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1770,"value":"class Surface {\n constructor (){\n this.q = 100\n this.height = this.q * 4\n this.width = this.q * 5\n\n this.x = d3.scaleLinear([-2, 2], [0, this.width + 28])\n this.y = d3.scaleLinear([-2, 1], [this.height, 0])\n this.thresholds = d3.range(1800, 4600, 50).map(i => i);\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1773,"value":"surface = new Surface()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1747,"value":"color_palette = {\n var color_palette = {};\n // Define palette for gaussians\n color_palette.color_gauss = d3.scaleSequential(d3.extent(surface.thresholds), d3.interpolateBuGn)\n // Define palette for portfolio\n color_palette.color_portfolio = d3.scaleSequential(d3.extent(surface.thresholds), d3.interpolateReds)\n // Define palette for competitor\n color_palette.color_competitor = d3.scaleSequential(d3.extent(surface.thresholds), d3.interpolateReds) // interpolateBlues\n // Define palette for attractor\n color_palette.color_attractor1 = d3.scaleSequential(d3.extent(surface.thresholds), d3.interpolateBlues)\n // Define palette for attractor\n color_palette.color_attractor2 = d3.scaleSequential(d3.extent(surface.thresholds), d3.interpolateGreens)\n // Define palette for attractor\n color_palette.color_attractor = d3.scaleSequential(d3.extent(surface.thresholds), d3.interpolateGreens)\n return color_palette\n};","pinned":false,"hidden":false,"mode":"ojs"},{"id":1060,"value":"md`\n# Functions`","pinned":false,"hidden":false,"mode":"ojs"},{"id":754,"value":"line_distance = d3.line()\n .defined(d => !isNaN(d.capacity))\n .x( d => PlotVariables.xScaleDist(d.capacity))\n .y( d => PlotVariables.distanceScale(d.distance/30));","pinned":false,"hidden":false,"mode":"ojs"},{"id":765,"value":"line_distance_horizontal = d3.line()\n .defined(d => !isNaN(d.capacity))\n .x( d => PlotVariables.xScaleDist(d.capacity))\n .y( d => PlotVariables.distanceScale(distance));","pinned":false,"hidden":false,"mode":"ojs"},{"id":850,"value":"line_distance_border_h = d3.line()\n .defined(d => !isNaN(d.capacity))\n .x( d => PlotVariables.xScaleDist(d.capacity))\n .y( d => PlotVariables.distanceScale(config.max_y_axis));","pinned":false,"hidden":false,"mode":"ojs"},{"id":758,"value":"$$a0 = {\n svg_distance.line\n .attr(\"d\", line_distance);\n svg_distance.line_horizontal\n .attr(\"d\", line_distance_horizontal);\n svg_distance.line_vertical\n .attr(\"d\", line_distance);\n svg_distance.line_border_h\n .attr(\"d\", line_distance_border_h);\n svg_distance.line_border_v\n .attr(\"d\", line_distance);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":611,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":1991,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":621,"value":"plotVar = new PlotVariables()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1995,"value":"plotAxis = new PlotAxis()","pinned":false,"hidden":false,"mode":"ojs"},{"id":37,"value":"function point(svg, coord, colour, config){\n svg\n .append('rect')\n .attr('x', config.scale_factor_routes*coord[0] + config.left_margin - config.node_size/2)\n .attr('y', config.scale_factor_routes*coord[1] + config.top_margin - config.node_size/2)\n .attr('height', config.node_size)\n .attr('width', config.node_size)\n .attr('fill', colour)\n .attr('stroke', 'black')\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":92,"value":"$38","pinned":false,"hidden":false,"mode":"ojs"},{"id":1628,"value":"updateDash = {\n const percentageOffset = new Array(1000).fill(1);\n const dashSeparation = 3;\n\n function updateDash() {\n svg_status_multipath.selectAll(\"path.link\")\n .style(\"stroke-dashoffset\", function (d, i) {\n percentageOffset[i] = percentageOffset[i] - .02;\n return percentageOffset[i] * dashSeparation\n })\n .style('stroke-width', (d, i) => 2)\n .style('stroke-dasharray', function(d, i){ \n const l = dashSeparation\n return 3 // 2px out of every l is a dash repeats 4 times\n });\n\n svg_large.selectAll(\"path.link\")\n .style(\"stroke-dashoffset\", function (d, i) {\n percentageOffset[i] = percentageOffset[i] - .02;\n return percentageOffset[i] * dashSeparation\n })\n .style('stroke-width', (d, i) => 2)\n .style('stroke-dasharray', function(d, i){ \n const l = dashSeparation\n return 3 // 2px out of every l is a dash repeats 4 times\n });\n \n }\n return updateDash\n} ","pinned":false,"hidden":false,"mode":"ojs"},{"id":1655,"value":"$$animateDash = {\n console.log(\"I created an interval\")\n let interval = setInterval(() => updateDash(), 6);\n \n invalidation.then(() => {\n console.log(\"I was invalidated.\")\n clearInterval(interval)\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":226,"value":"function background_rectangle(svg, config){\n svg\n .append('rect')\n .attr('x', 0)\n .attr('y', 0)\n .attr('height', config.total_frame_y)\n .attr('width', config.total_frame_x)\n .attr('fill', config.colours.bg3)\n .attr('stroke', 'black')\n}\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":1039,"value":"md`# Data Collection`","pinned":false,"hidden":false,"mode":"ojs"},{"id":439,"value":"function getData(name) {\n return fetch(`https://play-ml.datasparq.ai/api/data/vehicle-routing/${name}.txt`, { mode: 'cors' })\n .then(r => {\n console.log(\"response.status\", r.status, r)\n return r.json()\n })\n .then(d => {\n console.log(d)\n return d[name]\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":472,"value":"class DataConnections {\n constructor(){\n this.data_connections1 = getData('data_connections_capacity10')\n this.data_connections2 = getData('data_connections_capacity20')\n this.data_connections3 = getData('data_connections_capacity30')\n this.data_connections4 = getData('data_connections_capacity40')\n this.data_connections5 = getData('data_connections_capacity50')\n this.data_connections6 = getData('data_connections_capacity60')\n this.data_connections7 = getData('data_connections_capacity70')\n this.data_connections = [\n this.data_connections1,\n this.data_connections2,\n this.data_connections3,\n this.data_connections4,\n this.data_connections5, \n this.data_connections6, \n this.data_connections7\n ]\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1621,"value":"dc = new DataConnections()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1708,"value":"data_connections = dc.data_connections[capacity-1]","pinned":false,"hidden":false,"mode":"ojs"},{"id":768,"value":"distance = data_distance[capacity-1].distance/30","pinned":false,"hidden":false,"mode":"ojs"},{"id":779,"value":"distance_vector_vertical = [{capacity: capacity, distance:0}, {capacity: capacity, distance: 30*config.max_y_axis}]","pinned":false,"hidden":false,"mode":"ojs"},{"id":881,"value":"distance_vector_border_v = [{capacity: config.max_x_axis, distance:0}, {capacity: config.max_x_axis, distance: 30*config.max_y_axis}]","pinned":false,"hidden":false,"mode":"ojs"},{"id":57,"value":"set_locations = {\n // points\n const p1 = [1, 13];\n const p2 = [12, 9];\n const p3 = [21, 4];\n const p4 = [33, 5];\n const p5 = [30, 12];\n const p6 = [38, 16];\n const p7 = [17.4, 20];\n const p8 = [5, 22];\n const p9 = [10, 27];\n const p10 = [2, 31];\n const p11 = [17, 32];\n const p12 = [33, 23];\n const p13 = [42, 26];\n const p14 = [25, 28];\n // Return\n return [p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":106,"value":"connection_layout = [[0, 1], [1, 2], [2, 3], [3, 4], [0, 7], [7, 9], [7, 8], [0, 6], [11, 13], [6, 11], [6, 4], [5, 12],\n [4, 5], [5, 11], [11, 12], [12, 13], [13, 6], [6, 10], [10, 8], [9, 10], [9, 8], [2, 4], [4, 11], [3, 5], \n [1, 6], [7, 1], [10, 13], [1, 4]]","pinned":false,"hidden":false,"mode":"ojs"},{"id":408,"value":"$39","pinned":false,"hidden":false,"mode":"ojs"},{"id":441,"value":"data_locations = getData(\"data_locations\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":798,"value":"data_distance = getData(\"data_distance\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":1327,"value":"md`---\n# Data Collection Large`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1331,"value":"function getDataLarge(name) {\n return fetch(`https://play-ml.datasparq.ai/api/data/vehicle-routing-v2/routes/${name}.txt`, { mode: 'cors' })\n .then(r => {\n console.log(\"response.status\", r.status, r)\n return r.json()\n })\n .then(d => {\n console.log(d)\n return d[name]\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1516,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs"},{"id":1537,"value":"dcl = new DataConnectionsLarge()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1681,"value":"data_connections_large = dcl.data_connections[(number_stops-9) + 6*(hour_window-2)/2].then(data =>{return data})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1334,"value":"data_locations_large = getDataLarge(\"data_locations\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":1860,"value":"cost_vector = getDataLarge(\"cost_routes\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"md`# Imports and Plots`","pinned":false,"hidden":false,"mode":"ojs"},{"id":479,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs"},{"id":366,"value":"function svg_status(locations, connections) {\n const svg = d3.select(DOM.svg(config.total_frame_x, config.total_frame_y));\n // Background\n background_rectangle(svg);\n // Connections\n for (var i = 0; i < connections.length; i++) {\n add_link(svg, locations, connections[i], config.colours.link);\n }\n // Points\n for (var i = 0; i < locations.length; i++) {\n point(svg, locations[i], config.colours.node);\n } \n return svg.node()\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1206,"value":"function svg_status_v2(locations) {\n const svg = d3.select(DOM.svg(config.total_frame_x, config.total_frame_y));\n // Background\n //svg.style('background-image', 'url(\"https://images.fineartamerica.com/images-medium-large-5/3-london-england-street-map-michael-tompsett.jpg\")')\n svg.style('background-image', 'url(\"https://play-ml.datasparq.ai/api/data/vehicle-routing/central_london.jpg\")')\n \n \n svg.style('background-size', '100% 100%')\n \n svg\n .append('rect')\n .attr('x', 0)\n .attr('y', 0)\n .attr('height', config.total_frame_y)\n .attr('width', config.total_frame_x)\n .attr('fill', '#00000000')\n .attr('stroke', 'black')\n //\n point(svg, locations[0], '#000000', config)\n // Points\n for (var i = 1; i < locations.length; i++) {\n point(svg, locations[i], '#ff0000', config);\n } \n \n return svg.node()\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":500,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs"},{"id":1640,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs"},{"id":624,"value":"function axisTransform(g) {\nreturn g.selectAll('.tick text')\n .attr('font-size', 18)\n .attr('font-family', 'serif')\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":31,"value":"$3e","pinned":false,"hidden":false,"mode":"ojs"},{"id":28,"value":"config = new Config()\n//config = new Config(15, 16, 50, 50, 50, 5, 55, 33, 7, '#FFFFFFAA')","pinned":false,"hidden":false,"mode":"ojs"},{"id":1355,"value":"config_large = new Config(19, 8.5, 50, 50, 10, 5, 55, 33, 7, '#FFFFFFAA') \n//config_large = new Config(20, 9, 50, 50, 10, 5, 55, 33, 7, '#FFFFFFAA') ","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"import {slider, button, select, text, radio, checkbox, number} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"d3 = require(\"https://d3js.org/d3.v5.min.js\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":21,"value":"d3_file = require('d3-dsv')","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W3f","stdlib":"1","titling":"auto"}