Polyhedron Use Case

Last-Mile Delivery Vehicle Routing

Discover how we collaborate with customers to model and solve complex problems such as the Vehicle Routing Problem with time windows. This example shows our joint approach to transforming real business challenges into efficient solutions.

Back to Polyhedron

Complete Vehicle Routing Implementation

This example demonstrates our approach to building and solving real-world enterprise problems. We work closely with customers to understand their unique challenges and create tailored optimization models that deliver advanced classical and quantum-ready solutions.

Import Libraries and Setup

A Portfolio of Modeling Libraries

We begin by importing the essential Polyhedron components for graph modeling, spatial calculations, and QUBO compilation - one of our own toolkits for tackling complex optimization problems.

import pandas as pd
from polyhedron import Graph, GraphEdge, GraphNode, Model
from polyhedron.spatial import DistanceMatrix, Location
from polyhedron_pro.qubo import QuboCompiler, QuboCompilerSettings

Model Abstraction

Define Domain Classes

We define custom classes that represent the key elements of our routing problem: RouteArc for connections between locations with travel costs, and Stop for delivery points with time windows and service requirements.

class RouteArc(GraphEdge):
  used = Model.BinaryVar()    # 1 if arc is used in route
  travel_time: object         # scenario-based
  cost: float                # Cost of traversing this arc

  def objective_contribution(self):
    return self.cost * self.used

class Stop(GraphNode):
  arrival_time = Model.ContinuousVar(min=0, max=1000)
  sequence = Model.IntegerVar(min=0, max=10000)
  node_id: int
  demand: float
  service_time: float
  time_window_start: int
  time_window_end: int
  is_depot: bool = False

Defining Scenarios and Uncertainty

Load Data and Build Scenario Matrix

In this example, we define a distance matrix that accounts for travel time uncertainty. We ensure to capture relevant real-world operational constraints:

  • •Location Mapping: We create location objects for depot and all customer sites to establish the routing network
  • •Scenario Planning: We build multiple travel time scenarios (optimistic, most likely, pessimistic) with assigned probabilities to handle real-world variability
  • •Matrix Population: We fill the distance matrix with travel times between all location pairs, drawing from your historical data or routing APIs
# Build scenario matrix with different travel time scenarios
scenario_matrix = DistanceMatrix()
scenario_matrix.add_scenario("optimistic", weight=0.2)
scenario_matrix.add_scenario("most_likely", weight=0.6)
scenario_matrix.add_scenario("pessimistic", weight=0.2)

# Populate matrix with scenario values from input data
for row_id, row in time_matrix_most_likely.iterrows():
  for col_id, value in row.items():
    scenario_matrix.set_scenarios(
      locations[int(row_id)], locations[int(col_id)],
      {
        "optimistic": float(time_matrix_optimistic.loc[row_id, col_id]),
        "most_likely": float(value),
        "pessimistic": float(time_matrix_pessimistic.loc[row_id, col_id]),
      }
    )

Defining the Logic

Add Core Constraints

We implement the fundamental business rules that make operations feasible and practical, ensuring every constraint from your operations is properly modeled. In this particular example:

  • •Service Coverage: Guarantee each customer location is visited exactly once, preventing missed deliveries or duplicate visits
  • •Time Window Compliance: Ensure deliveries arrive within your customers' specified time slots, respecting both start and end times
  • •Route Continuity: Model how time accumulates along delivery routes, accounting for travel time, service time, and sequence dependencies
  • •Logical Consistency: Use conditional constraints to ensure time propagation only applies when routes are actually used
@model.constraint(name="customer_service")
def customer_service():
  # Each customer must be visited exactly once
  return [sum(edge.used for edge in edges if edge.target == customer) == 1
            for customer in customers]

@model.constraint(name="time_windows", foreach=customers)
def time_windows(customer: Stop):
  # Respect customer time windows
  return [customer.arrival_time >= customer.time_window_start,
            customer.arrival_time + customer.service_time <= customer.time_window_end]

@model.constraint(name="time_propagation", foreach=edges)
def time_propagation(edge: RouteArc):
  # Time accumulates along the route
  if edge.target.is_depot:
    return []
  return (edge.target.arrival_time >=
            edge.source.arrival_time + edge.source.service_time + edge.travel_time
            - big_m + edge.used * big_m)

Powerful Backend Abstraction

Classical & Quantum Execution

With the power of Polyhedron's unique dual-execution capability, we can materialize your optimization model to run on advanced classical optimizers, or compile it to quantum computing hardware - supporting both gate-based quantum computers and quantum annealing systems:

  • •Flexible Execution: Choose between classical optimization engines or quantum computing platforms based on your needs and available hardware
  • •Unified Framework: Single model definition that automatically adapts to run on classical solvers or quantum hardware
# Compile to QUBO for quantum annealing
compiler = QuboCompiler(QuboCompilerSettings(
  continuous_step=1.0,      # Discretization step
  penalty_weight=10.0       # Penalty strength
))
compilation = compiler.compile(model)
qubo, offset = compilation.to_qubo()

# Solve the model
result = model.solve(time_limit=60)