Overview

_images/map_perspective.png

What it is

KangRouter solves a hard variant of the Vehicle Routing Problem that features:

Pickup and Delivery
It focus on planning the transportation of cargo/passengers between prearranged pairs of locations - the origin (pickup) and destination (delivery).
Time Windows
Time windows may be used to bound the time in which pickups/deliveries must occur. This supports most common time constraints, such as “must arrive before than”, “must depart no later than”, etc.
Multiple Vehicles
A fleet of multiple heterogeneous vehicles is considered.
Capacities
Specific vehicle configurations and custom cargo/passenger transportation requirements are taken into account. This allows to specify resource availability such as “I have an Ambulance with room for 2 wheelchairs and 4 regular seats” and resource consumption, for example “I need an Ambulance with room for 1 wheelchair”.
Depots
Each vehicles begin/ends at a specific preset location (its depot).
Vehicle/Driver Availabiliy
Time windows may be used to bound the part of day at which a given vehicle is operational. Additionally, the total amount of work time may be constrained as well. These model vehicle and/or driver availabilities.
Work Breaks
Work breaks may be modelled by specifying a time window in which the work break must occur and the duration of the work break. Multiple work breaks by vehicle/driver are permitted.
Routing Engine
KangRouter has a builtin routing engine for computing travel durations and distances between locations.
Efficiency
KangRouter finds efficient plans for problems with dozens of vehicles and hundreds of locations within minutes.

What it isn’t

Distribution
A large class of VRP variants focus on matching supply/demand levels. In these problems, finding where to pickup and deliver goods in order to satisfy supply/demand constraints is part of the problem. This contrasts with our problem, in which each item must be carried from a preset known location to another.

How it works

A Job is the transportation of cargo/passengers from one location to another. KangRouter takes as input a list of jobs and a list of vehicles that are available for performing those jobs, as well as a list of constraints affecting those jobs and vehicles, as described above. The optimization algorithm then searches for the feasible plan that maximizes the number of jobs served in the shortest amount of time. The output is an assignment of jobs to vehicles, and an ordering of the locations to visit for each vehicle.

A tiny example

Consider the following problem with only two jobs:

  • Taking Alberto Caeiro home after a medical appointment at the Garcia de Orta Hospital. He is ready to leave the hospital after 13:00, and must be home no later than 14:15. Alberto is on a wheelchair, so we allocate 5 minutes for pickup and dropoff.
  • Picking Ricardo Reis at the Brasileira café, and take him to a beach restaurant. He wants to be there no later than 12:15. He takes a regular seat.

Assume that there is only one vehicle available for transportation, and it is parked in Sintra, has 3 seats and room for 2 wheelchairs. Additionally, the driver must have a 60 minute lunch break between 12:00 and 14:00.

For the above input, KangRouter produces the following plan:

Event Location Min.Time Max.Time Vehicle
Leave depot Sintra 10:37 11:38 1
Pick Ricardo Brasileira 10:58 11:59 1
Drop Ricardo Beach 11:14 12:15 1
Have Lunch   12:00 12:55 1
Pick Alberto Hospital 13:00 13:55 1
Drop Alberto Home 13:20 14:15 1
Go to depot Sintra 13:40 14:35 1

A plan is therefore a series of events (a pickup, delivery, or the start of a work break), ordered chronologically for each vehicle. Each event aggregates information about the geographic location of the event (Location), the vehicle assigned to the event (Vehicle), and the time window in which the event is planned to occur (Min.Time, Max.Time).

This problem is illustrative and obviously very simple - it gets much more challenging with a few more jobs and vehicles.

How to use

The software runs in the cloud, on a time subscription basis. It comes in two shapes:

KangRouter Engine
Essentially just the planning algorithm with a really simple RESTful interface that allows to upload a problem and download its solution, as well as monitoring the solving process. For convenience, Python and Javascript client libraries are also available.
KangRouter UI (Comming soon)
A human friendly interface to the planner, assisting the user in data importing/exporting, validation, and inspection. The application runs on recent versions of all major browsers.