Understanding the Routing Playground

Owned by eknoor.singh (Unlicensed)
Nov 14, 2023
11 min read

Introduction

Using this document, users will be able to gain a deeper understanding of how the routing playground works and how they can use it to optimise their operations.

Navigating to the Routing Playground

  1. Click on the hamburger menu icon

  2. Select Shipsy AI

  3. Click on Routing Playground from the sub menu

Selecting the Relevant Tab to Navigate to

Here, the user can choose between three sub-tabs

  1. Simulate - Where users can configure the strategy and parameters of optimisation for a hub from scratch, or use existing configurations to run simulations and examine the outputs

  2. Visualise - Previously saved outputs that were run in the simulations can be viewed here

  3. Partition - This tab can be used to demarcate partitions around a given hub as per requirements

Simulating a Strategy in the Simulate Tab

  1. The Simulate tab helps to both set the optimization strategy for a particular hub and running simulation on the same

  2. On this screen, a user can see the following things:

    1. Hub: User can select the hub for which the simulation is to be done, or the strategy is to be set.

    2. Save Configuration: Save and store the created configuration within Shipsy

    3. Apply: Apply the created configuration for routing

    4. Run: Run the simulation to see whether the configuration solves the business requirements or not

    5. Import: Import strategy parameters from some other configuration, import consignments and vehicles from some other configuration, or import both

    6. Export: Export configuration parameters in the form of a json

Configuring the Necessary Parameters

  1. The following are the Parameters (params) that users may have to configure:

    1. Consignment Parameters

    2. Vehicle Parameters

    3. Organisation Parameters

    4. Map Details

  2. However, before going further, it is important to understand some important terminology that is being used in this document.

Common Input Parameters

  • In Range (IR): Generate values for an entry within (min-max) range.

  • Random From (RF): Select random values from the given set of values.

  • Fixed in Order (FIO): The entry is assigned values in the specified order. In the following example, the first consignment’s entry has value 1. The second gets 2 and so on.

  • Constant (C): All consignments are assigned same entry values. For ex: Height of all consignment as 11 m.

  • Finally, some entries are typed manually. For ex: Address, Number of consignments and so on. We use no symbol to denote it.

Consignment Parameters

  1. User needs to fill in the mandatory and optional parameters for the selected strategy here. However, user can also import directly via Excel Upload

  2. A consignment can also be referred to as: “delivery”, “node”, “customer”. Assign the properties of the consignment or generate the consignment within a location range

  3. Number*: The number of consignments to that specific location.

  4. Weight*  (IR/FIO/RF/C):   Weight of each consignment.

  5. Volume*  (IR/FIO/RF/C):   Volume of each consignment.

  6. Height*   (IR/FIO/RF/C):  Height of each consignment.

  7. Latitude* (IR/FIO): Latitude of consignment address.

  8. Longitude* (IR/FIO): Longitude of consignment address. 

  9. Type*  (RF/FIO/C): The type of the node to serve { 'pickup', 'pickupanddelivery', 'delivery', 'pickupanddeliveryreverse'}

  10. Address String: Address of the node. This is used to combine consignments with the same address. This feature can be turned off/on via: “combine same address customers” options.

  11. Phone Number (RF/FIO/C): The number of consignments to that specific location. Use case is the same as above.

  12. Partition ID (RF/FIO/C): A unique number which segregates consignments into various partitions. Consignments of two different partitions are never clubbed together.

  13. Service Time* (IR/FIO/RF/C): Time in seconds a vehicle will spend in a given node. 

  14. Time Window Open (FIO/RF/C): The opening time at which the node can be served.

  15. Time Window Close (FIO/RF/C): The closing time at which the node can be served. Delivery should happen within this window.

  16. Constraint Tags (RF/FIO): The constraint tags to be obeyed. The carrier vehicle’s constraint tag list should contain all the tags of the current node. Thus, only certain vehicles which satisfy all constraints can serve this node.

* Represents mandatory fields

Vehicle Parameters

  1. Next, the user needs to fill in the mandatory and optional parameters for the selected strategy here. Additionally, user can also import directly via Excel Upload

  2. Use these parameters to design the properties of a vehicle. A vehicle can also be referred to as: “worker”, “rider”.  Each vehicle has a capacity for: height, weight, consignment_count etc. Users are allowed to define constraints so that consignment demand does not exceed vehicle capacity. 

  3. As discussed before some consignments have special constraint tags, only vehicles which satisfy all constraints are allowed to serve it. 

  4. Vehicle attributes are as follows:

  5. Number*: The number of consignments to that specific location.

  6. Weight*  (IR/FIO/RF/C):   Weight of each consignment.

  7. Volume*  (IR/FIO/RF/C):   Volume of each consignment.

  8. Height   (IR/FIO/RF/C):  Height of each consignment.

  9. Speed (IR/RF/FIO): The average speed of the vehicle in km/hr.

  10. Distance* (IR/FIO/C): The maximum distance in km a vehicle can travel hub-to-hub

  11. Consignment Capacity* (FIO/IR/C): The maximum number of consignments a vehicle can carry at any time. 

  12. Priority (RF/FIO/IR/C): The priority of vehicle usage.

  13. Delivery Time Start (FIO/C): Vehicle time window start in HH:MM

  14. Delivery Time End (FIO/C): Vehicle time window end in HH:MM

  15. Constraint Tags (FIO/RF):  Vehicle can carry consignments whose constraint tags are a subset of it. For example: A customer may have a “handle with care” item as consignment. It doesn’t make sense to lump this consignment with vehicles carrying non-sensitive items as it could lead to breakage.

* Represents mandatory fields

Optimization Parameters

  1. The next step is to configure the optimisation parameters. Each strategy may/may not use all the parameters defined below

  2. Multiple hub visits allowed: Are vehicles allowed to visit hub multiple times a day.

  3. Constraint Type:   Constraint to consider when delivering consignments {"number", "volume", "weight", "tags", "time", "height", "service_time" }.

  4. Service Time Per Demand:  Time taken to fulfil a demand at a node.

  5. Combine Same Address Customers : Boolean, self explanatory.

  6. Add Service Time : Add service time of the clubbed consignments, else consider the maximum of all clubbed consignments

  7. Use Partition Template: Boolean, allow automatic partition ID generation. Set partition_id_template for each customer, which gets stored as its partition ID. If use_partition_template is true, but template isn’t provided, then customer partition ID is chosen as default.

  8. Partition ID Template: Explained above. Specify the key in which the template is stored in the frontend. For ex:

Last consignment doesn’t have the key, so use current partitionID as fallback.

  1. Internal Manual Partition Map: Takes current customer partitionID and maps it into another partitionID. The hash-map must be manually specified. For ex:

  1. Use Manual Partitions : Boolean. Allow using the manual partition map.

  2. Default Vehicle Speed: Average speed of vehicle in km/hr.

  3. Vehicle Utilisation : A safety factor criteria. How much of the vehicle to use.

  4. Priority Tags: Nodes with priority tags are prioritised over non-tagged consignments

  5. Is Hyperlocal Request: Is the planning for a hyperlocal system. Cost function is prioritised for time in this case.

  6. Hyperlocal Customisation Params: Parameters defining hyperlocal trip.

    1. request_max_time: Time limit to serve a customer.

    2. SLA : Service level agreement for delivery time in seconds.

    3. global_span_coefficient: A coefficient which allows for more aggressive minimisation of coefficient.

    4. penalty_scaling_factor: Penalty for dropping a consignment.

  7. Use Hub Geofence Partitions: Use manually drawn polygon as geofence partitions.

  8. Generate Preference Id:  preference id's help create better looking clusters of consignments in a trip, but needs to be skipped in case of hyperlocal planning or if stated explicitly.

  9. Cost Customization Params: 

drop_cost_expression

Penalty expression  for dropping a consignment. Valid parameters:

  1. max_distance: Maximum distance between two nodes

  2. total_distance: Total distance travelled by a vehicle.

  3. customer: A customer object with the following attributes.

    customer = namedtuple('Customer', ['index_id', 'demand', // weight 'volume', 'lat', 'lng', 'tw_open', 'tw_close', 'consignments_count', 'service_time_per_demand', 'type', 'fuel_type', 'partition_id', 'height', 'preference_id', 'trip_id', 'task_type', // Real or dummy 'original_type', // {delivery, pickupanddelivery, pickup, pickupanddeliveryreverse} 'consignment_priority', 'constraint_tags'])

  4. min_speed_mps: Minimum vehicle speed in meters/second.

  5. vehicle_priority: Vehicle usage priority.

  6. hyperlocal_customization_params: A mapping of hyperlocal customization parameters. Explained later.

{ "drop_cost_expression" : "int(total_distance/min_speed_mps)" }

fixed_cost_expression

Fixed cost of using a vehicle.

  1. vehicle: An instance of  vehicle object. The following attributes may be accessed.

Vehicle = namedtuple('Vehicle', ['index', 'priority', 'capacity', 'volume_capacity', 'delivery_time_start', 'delivery_time_end', 'consignments_capacity','height','trip_id','vehicle_service_time','variable_cost','fixed_cost','constraint_tags', 'speed', 'task_capacity'])

  1. max_distance : Maximum distance between two nodes.

An example for fixed_cost_expression: 

arc_cost_expression

The primary objective function to minimise. Available params:

  1. vehicle: An instance of  vehicle object. The following attributes may be accessed. See above for valid attributes.

  2. from_node:  The source customer node being considered during the optimization loop.

  3. to_node: The destination customer node being considered during the optimization loop.

  4. dist_mat: A matrix storing distance between customer nodes.

An example for fixed_cost_expression: 

Use Geofence Partition as Tags

Use the manually drawn partition as a consignment tag.

Map details

Map details are used for creating partitions in the map and assigning ID to them. First enable Use Hub Geofence Partitions.  Then manually create a polygon region via selecting points in a map.

Strategies

The routing playground offers a multitude of optimization strategies.

To begin with,

  1. Select the hub to configure.

  2. Set the inputs and follow the instructions to run an example.

Vehicle Routing Open-source Optimization Machine (VROOM)

VROOM is an open-source optimization engine that aims at providing good solutions to various real-life vehicle routing problems (VRP) within a small computing time.

Pros

  • Solve several well-known VRPs like TSP, CVRP, VRPTW, MDHVRPTW (multi-depot heterogeneous vehicle VRPTW), PDPTW (pickup-and-delivery problem with TW)

  • Can use a custom cost matrix and works out-of-the-box on top of several open-source routing engines like OSRM, Valhalla

  • Good solutions within small computing times.

  • Can scale to handle big instances.

  • Could be a good alternative of OR-TOOLS

  • Can handle a larger set of constraints

Cons

  • Fewer options for optimatization criteria can be given to vroom.

  • Consignment priority is limited, only integer [1,100]

Shipsy Clustering Algorithm

A simple clustering algorithm. Segregates customers into clusters based on their partitionID. Collects all the feasible nodes and groups the closest together. At the end, a TSP algorithm is applied to each cluster to get an optimal route per cluster.

Pros

  • quick planning

  • can handle larger scale of consignments

  • intuitive looking trips

Cons

  • routes are not the most optimal

  • time slots for deliveries are not considered

Google OR Tools

Uses Google OR Tools, a constraint optimization library. Searches in the set of feasible solutions for x amount of time. Returns the best solution found so far.

Pros

  • Most cost efficient solution: Returns the best feasible solution found within the provided time frame.

  • Custom cost expression: User can explicitly set cost expression to optimize for.

  • Highly configurable: Allows setting all kinds of constraints.

Cons

  • Unintuitive travel path: Most optimal path may not be most intuitive.

  • Slow: Relatively slower than all other algorithms.

  • Limit: Cannot work on large number of consignments (> 1500).

Simple Balanced K means

Segregates customers based on their partition ID. This is followed by assigning the number of clusters to each partition. A vehicle is said to serve a cluster in a partition. Number of clusters is determined by vehicle capacity. Finally, the order of visit per vehicle in a cluster is deduced via TSP algorithm. 

If `number` is a constraint, then it drops excess of the consignments.

Pros

  • Quick planning.

  • Can handle  larger scale of consignments.

  • Intuitive looking trips.

Cons

  • Routes are not the most optimal

  • Time slots for deliveries are not considered

  • No other constraint other than vehicle consignment capacity is considered

Use All Vehicles No Constraints

Same as above but the number of clusters is assigned so as to maximise vehicle utilisation.

Visualising a Configuration in the Visualise Tab

Using the Visualise Tab, users can upload up to 4 already configured strategies. To do so, the user must upload one or multiple outputs as per their requirements and click on the Visualise button.

Plotting Hub Partitions using the Hub Partition Tab

Lastly, the user can draw polygons manually to create partitions around hubs using the Hub Partition tab. To do so, the user needs to follow the below mentioned steps:

  1. Select the hub they want to draw partitions around from the Hub Selection dropdown on the top left corner of the screen

  2. Select the algorithm they want to use for this purpose

  3. Zoom in on the map and click on a point from where they want to start plotting their polygon from

  4. From here, the user can plot as many points on the screen as they want to and a colour-coded polygon will be plotted along those points

  5. Users can plot as many points as they want to

  6. To stop plotting and finalise the given polygon, user needs to double click on the last point

  7. A pop-up appears with the list of partitions the user has created named as partition_1, partition_2 and so on

  8. User can rename or delete these partitions as per their requirements

  9. Finally, the user should click on the save button in the top right corner of the screen to save their partitions within the system.