Ride Dispatch Orchestration
Introduction
NearMe operates a ridesharing shuttle service, and while building its dispatch routing, we noticed something interesting. It has a structure that resembles the cloud infrastructure technique known as “container orchestration.”
Container orchestration is a technique for managing applications that run in computing environments in units called containers, allocating computing resources appropriately, and making them work together cooperatively.
Kubernetes is a representative tool for container orchestration. Here, we will focus on the analogy between k8s and dispatch routing.
Building Blocks
In k8s, there is a hierarchy of containers, pods, and nodes. A container is the runtime environment that executes a single application. A pod groups multiple closely related containers. Containers are managed at the pod level together with their shared resources. A node represents one physical server or virtual machine, and multiple pods are placed on and executed on top of it.
On the other hand, dispatch routing has hierarchical building blocks such as passengers/baggage, orders, and vehicles. Passengers and baggage are the smallest units of cargo. An order requests transportation for multiple passengers or pieces of baggage. A vehicle, especially when ridesharing is allowed, operates by grouping multiple orders together.
Scheduling
In k8s, a scheduler assigns each pod to the best node while taking various constraints and evaluations into account. For example, when a pod is created, it searches for nodes with available resources and assigns the pod so that resource usage is balanced across nodes. The scheduler can also be extended in a plug-in-like way, and there are tools such as descheduler that remove pods and reschedule them.
In dispatch routing, too, there is a scheduler that assigns each order to a vehicle based on various considerations. For example, when an order comes in, it searches for assignable vehicles based on detour time, waiting time, vehicle capacity, and so on, and assigns the order so that the overall route becomes shorter (reference). At that time, existing orders may also be reassigned across vehicles (reference).
Autoscaling
In k8s, when pods cannot be scheduled because of insufficient resources, nodes can be added automatically. Conversely, nodes can also be removed automatically when load is low.
In dispatch routing, as the number of orders increases, the number of required vehicles also increases. In particular, for advance reservations, it is possible to automatically increase the number of “virtual vehicles” and assign orders to them. Those virtual vehicles are later replaced with real vehicles. If a cancellation means that a vehicle is no longer needed, that vehicle is removed.
However, while k8s scales not only nodes but also pods, dispatch routing generally scales only vehicles. That said, the scaling of orders may be understood as a situation where multiple vehicles are reserved as a safeguard.
Resource Management
In k8s, you can specify the amount of each resource a container needs, such as CPU and memory. When a pod is created, the resource requirements of the containers belonging to that pod are aggregated, and if the resources cannot be secured, the pod cannot be assigned to that node.
In dispatch routing, by contrast, passengers and baggage occupy a certain number of seats or a certain amount of capacity. Some items, such as small children or large baggage, have different occupancy requirements on their own. Vehicles have a maximum number or amount of seats and trunk capacity, and if they cannot satisfy the number or amount required by the order, they cannot be assigned to that vehicle.
However, while k8s resource quantities can specify both minimum and maximum values, occupancy requirements in dispatch routing are generally the same for both: minimum = maximum.
Affinity
In k8s, the placement conditions for pods on nodes can be specified in detail using a method called affinity. For example, both nodes and pods can be given arbitrary labels, and pods can be assigned forcefully or preferentially to nodes with specific labels (node affinity), or assigned to nodes without specific labels (node anti-affinity). Pods can also be co-located with or kept away from nodes, zones, and other locations that contain pods with specific labels (pod affinity and pod anti-affinity). In addition, there is a mechanism that works somewhat in reverse of node affinity, where only specific pods can be assigned to specific nodes (node taints and pod tolerations).
In dispatch routing, for example, if an order includes requirements such as a child seat, a pet, or a wheelchair, it may be better to assign it to a specific vehicle (vehicle affinity). There may also be cases where, due to the operating area, we want to avoid assigning a certain order to a specific vehicle (vehicle anti-affinity). Furthermore, we may want to have people who are as familiar as possible ride together (order affinity), or not ride together (order anti-affinity). Some vehicles may only accept specific orders (vehicle taints and order tolerations).
Closing Thoughts
We have found analogies between container orchestration, especially k8s building blocks and scheduling mechanisms, and the dispatch routing for our ridesharing shuttle.
From this analogy, we hope to gain insights from the more refined world of k8s, even though it is a different domain, and use them to inform our dispatch routing implementation and organize our concepts. In fact, we imported concepts such as affinity from k8s and implemented them. We also drew inspiration from k8s’s declarative design, although it is not introduced here. Going forward, we believe k8s’s autonomous distributed behavior may also offer useful ideas.
Finally, NearMe is hiring engineers! Casual interviews are also available, so please feel free to contact us.
Author: Kenji Hosoda