Exemplo: matriz de atribuição

Entregue cada nova encomenda ao estafeta que a pode alcançar primeiro, com tempos de viagem reais em vez de distâncias em linha reta.

Nesta página

Como funciona
O código
O que mostra
Adaptá-lo

As novas encomendas chegam; os estafetas estão espalhados pela cidade. A distância em linha reta é um mau guia em Lagos ou em Acra: o estafeta mais próximo pode estar do outro lado de uma lagoa, ou do lado errado de uma via rápida sem inversão de marcha durante três quilómetros. Este exemplo pede à matriz de percursos o tempo real de viagem de cada estafeta livre até cada encomenda pendente, num único pedido, e depois entrega cada encomenda ao estafeta que chega primeiro.

Como funciona

Reúna as últimas posições dos estafetas livres (da sua aplicação de estafetas, ou do seguimento de frota) e os pontos de recolha das encomendas pendentes.
Envie os estafetas como origins e os pontos de recolha como destinations para POST /maps/v1/routes/matrix: até 50 de cada e 625 pares por pedido.
Percorra os pares do tempo mais curto para o mais longo, e fique com um par quando o estafeta e a encomenda ainda estão ambos livres (uma atribuição gulosa: simples, rápida e próxima do melhor resultado para a atribuição de viagens).
Descarte os pares que a matriz declara impossíveis (ROUTE_NOT_FOUND), e os que ultrapassam o prazo prometido ao cliente.

Nota:

O exemplo calcula as motas dos seus estafetas em dispatch: evitam as estradas fechadas a todas as motas, mas as proibições de okada comercial não se aplicam. Se os seus estafetas transportam passageiros (okadas), use okada: os pares numa zona proibida voltam então como NOT_ALLOWED.

O código

Execute-o no seu servidor com uma chave restrita ao endereço IP do servidor e à API Matriz de percursos. Node.js 18 ou mais recente, ou Python 3.8 ou mais recente, nada para instalar.

dispatch.mjs

// Entrega cada encomenda pendente ao estafeta livre que chega primeiro ao seu ponto de recolha.
// node dispatch.mjs   (NWAYS_API_KEY no ambiente)
const KEY = process.env.NWAYS_API_KEY
const MAX_MINUTES = 25 // não envie um estafeta mais longe do que isto

const riders = [
  { id: 'rider-ade', at: { lat: 6.6018, lng: 3.3515 } }, // Ikeja, Allen Avenue
  { id: 'rider-bisi', at: { lat: 6.5005, lng: 3.3581 } }, // Surulere
  { id: 'rider-chidi', at: { lat: 6.4474, lng: 3.4733 } }, // Lekki Phase 1
]
const orders = [
  { id: 'order-1041', pickup: { lat: 6.5965, lng: 3.3421 } }, // Ikeja GRA
  { id: 'order-1042', pickup: { lat: 6.4413, lng: 3.4250 } }, // Victoria Island
  { id: 'order-1043', pickup: { lat: 6.5095, lng: 3.3711 } }, // Yaba
]

async function matrix(origins, destinations) {
  const res = await fetch('https://nways.ng/maps/v1/routes/matrix', {
    method: 'POST',
    headers: { 'Content-Type': 'application/json', 'X-NWays-Api-Key': KEY },
    body: JSON.stringify({ origins, destinations, mode: 'dispatch' }),
  })
  const data = await res.json()
  if (!res.ok) throw new Error(`${res.status} ${data.error?.reason ?? ''}: ${data.error?.message ?? ''}`)
  return data.elements
}

const elements = await matrix(riders.map((r) => r.at), orders.map((o) => o.pickup))
const pairs = elements
  .filter((e) => e.status === 'OK' && e.durationS <= MAX_MINUTES * 60)
  .sort((a, b) => a.durationS - b.durationS)

const busy = new Set()
const done = new Set()
for (const e of pairs) {
  const rider = riders[e.originIndex]
  const order = orders[e.destinationIndex]
  if (busy.has(rider.id) || done.has(order.id)) continue
  busy.add(rider.id)
  done.add(order.id)
  console.log(`${order.id} → ${rider.id}: ${Math.round(e.durationS / 60)} min, ${(e.distanceM / 1000).toFixed(1)} km`)
}
for (const o of orders) if (!done.has(o.id)) console.log(`${o.id}: no free rider within ${MAX_MINUTES} min`)

dispatch.py

"""Entrega cada encomenda pendente ao estafeta livre que chega primeiro ao seu ponto de recolha.
python3 dispatch.py   (NWAYS_API_KEY no ambiente)"""
import json
import os
import urllib.error
import urllib.request

KEY = os.environ["NWAYS_API_KEY"]
MAX_MINUTES = 25  # não envie um estafeta mais longe do que isto

riders = [
    {"id": "rider-ade", "at": {"lat": 6.6018, "lng": 3.3515}},  # Ikeja, Allen Avenue
    {"id": "rider-bisi", "at": {"lat": 6.5005, "lng": 3.3581}},  # Surulere
    {"id": "rider-chidi", "at": {"lat": 6.4474, "lng": 3.4733}},  # Lekki Phase 1
]
orders = [
    {"id": "order-1041", "pickup": {"lat": 6.5965, "lng": 3.3421}},  # Ikeja GRA
    {"id": "order-1042", "pickup": {"lat": 6.4413, "lng": 3.4250}},  # Victoria Island
    {"id": "order-1043", "pickup": {"lat": 6.5095, "lng": 3.3711}},  # Yaba
]


def matrix(origins, destinations):
    body = json.dumps({"origins": origins, "destinations": destinations, "mode": "dispatch"}).encode()
    req = urllib.request.Request(
        "https://nways.ng/maps/v1/routes/matrix",
        data=body,
        headers={"Content-Type": "application/json", "X-NWays-Api-Key": KEY},
        method="POST",
    )
    try:
        with urllib.request.urlopen(req, timeout=20) as res:
            return json.load(res)["elements"]
    except urllib.error.HTTPError as e:
        err = json.load(e).get("error", {})
        raise SystemExit(f"{e.code} {err.get('reason')}: {err.get('message')}")


elements = matrix([r["at"] for r in riders], [o["pickup"] for o in orders])
pairs = sorted(
    (e for e in elements if e["status"] == "OK" and e["durationS"] <= MAX_MINUTES * 60),
    key=lambda e: e["durationS"],
)

busy, done = set(), set()
for e in pairs:
    rider, order = riders[e["originIndex"]], orders[e["destinationIndex"]]
    if rider["id"] in busy or order["id"] in done:
        continue
    busy.add(rider["id"])
    done.add(order["id"])
    print(f"{order['id']} -> {rider['id']}: {round(e['durationS'] / 60)} min, {e['distanceM'] / 1000:.1f} km")
for o in orders:
    if o["id"] not in done:
        print(f"{o['id']}: no free rider within {MAX_MINUTES} min")

O que mostra

Algo como isto:

Text

order-1041 → rider-ade: 6 min, 2.1 km
order-1043 → rider-bisi: 9 min, 3.0 km
order-1042 → rider-chidi: 14 min, 6.2 km

Adaptá-lo

Mais de 50 estafetas ou encomendas? Divida os estafetas em grupos de 25 e as encomendas em grupos de 25, e peça uma matriz para cada par de grupos (625 pares cada).
Agrupamento. Para entregar várias encomendas a um estafeta pela melhor ordem, use antes a otimização de percursos.
Equidade. Antes de ordenar, acrescente uma pequena penalização aos estafetas que acabaram de fazer uma viagem longa, ou que já fizeram mais viagens do que os outros hoje.
Custo. A matriz é faturada por par (elemento): 3 estafetas × 3 encomendas são 9 elementos. Preços