Problem Origin and Background

Delivery of soft drinks to small and medium sized retailers in São Paulo:

1. Time windows for delivery ⇒ variation of the VRPTW
2. High-density populated region
3. Congested streets and scarcity of parking lots

Motivation

• Additional applications
  • Delivering small (portable) packages (eg. mail)
  • Particularly interesting in (limited time) pedestrian areas
  • Mitigates effects of rush hours and congestion
• Cost reduction and sustainability
  • Reduces cost on vehicles, fuel, inner city tolls, ...
  • Implicitly incorporates green objectives
• Clustering is required
  • Cluster assignment problem and routing are not independent
  • Otherwise, outer routing algorithms essentially useless for practical purposes
• Assumptions
  • Deliveries are portable by a single worker
  • Only direct delivery between parking and customers
  • Cluster service time and time windows depend on inner schedule
  • Customers are serviced by one worker
  • Additional workers do not reduce service times at customers
  • Additional workers allow servicing customers in parallel
  • Designated parking spaces are not occupied

• Customer Scheduling
  • Scheduling is also NP-hard
  • Fast heuristic needed
  • Ideally, the heuristic can be incorporated in a scheduling + outer routing learning process
• Objective function is $$\min C(t, s, d) = t \cdot c_t + s \cdot c_s + d \cdot c_d$$
  • Different scheduling solutions can have the same (optimal) objective function value

  • $t$

    number of trucks

    $s$

    number of service workers

    $d$

    total distance driven by all trucks

    $c_t$

    fixed cost per truck

    $c_s$

    fixed cost per service worker

    $c_d$

    cost per distance unit

Goals

1. Identification of required algorithmic components
2. Creation of realistic benchmark instances
3. Implementation and systematic evaluation of these heuristics

New Benchmark Instances

• Solomon instances do not reflect problem characteristics
  • Some customers may have a parking
• Defined data interchange format using JSON schema
  • Human readable
  • Instances are easy to read in almost any programming language
• Added additional meta-data like the serialized best known solution
  • Single ASCII string
  • Clients, parkings and the depot are denoted by their integer id
  • Clusters are denoted by the id of their parking location, followed by a comma (','), followed by all clients in the cluster in the order they are processed (which might be in parallel) separated by commas
  • Clusters are written in order they are visited on a route and separated by semicolons (';')
  • Routes/ Trucks are encoded by the number of workers on the route followed by a semicolon followed by the starting depot; then all clusters are listed, separated by semicolons and followed by the closing depot
  • Routes are separated by a single space
  • Additional whitespace is forbidden in solution strings
  • Example: '3;0;8,2,5,7;10,6;0 2;0;1,1,4;9,3;0'

• 54 representative instances
  • Each instance has 200 clients
  • 27 regionally clustered + 27 randomly distributed
  • Instances with 50, 100 and 150 parking locations
  • Tight, normal and wide time windows
  • Low, normal and fast walking speed in relation to driving speed
• Example

  • {
      "name": "presentation 3",
      "description": "This instance is for presentation/ demo purposes. It can also be used to test the efficiency of algorithms as it is designed with an optimal solution in mind. It can be solved with three trucks - one with one, the second with two and the third with three service workers. Parking at the customer sites is forbidden by an extremely high penalty.",
      "truckCapacity": 100.0,
      "costTruck": 1.0,
      "costWorker": 0.1,
      "costDistance": 0.0001,
      "bestKnownTrucks": 3,
      "bestKnownWorkers": 6,
      "bestKnownDistance": 410.9302842022,
      "bestKnownCost": 3.6410930284,
      "bestKnownSolution": "3;0;1,6,10;2,5;3,8,12,11,14;4,9,13,7;0 2;0;15,21,27,23,30;18,28,25,24;16,20,26;19,22;17,29;0 1;0;31,47,43;35,40;32,45,49;36,41;31,48;33,46,42,44;0",
      "optimumKnown": true,
      "depot": { "id": 0, "x": 0.0, "y": 0.0, "est": 0.0, "lst": 480.0},
      "parkings": [
        { "id":  1, "x": -29, "y": -31 },
        ...
        { "id": 39, "x":  -1, "y":  36 }
      ],
      "clients": [
        { "id":  5, "x": -39, "y":  -9, "demand": 10, "est":   0, "lst": 240, "st": 5 },
        ...
        { "id": 49, "x":  53, "y":  -9, "demand": 10, "est":   0, "lst": 480, "st": 5 }
      ]
    }
    

Clustering Customers

• Currently: cluster first, route second

• Clusters are built in parallel - one client at a time

• Each cluster keeps track of its service time and earliest and latest start
  • A minimum amount of workers may be required
  • Service time and earliest and latest start are calculated for each possible number of workers
  • Outer routing algorithm gets the clusters as black boxes

• Created MIP model
  • Parameters

    $N$

    set of customers ($n \in N$)

    $P_0$

    set of parking sites including the depot ($p \in P_0$)

    $M$

    set of customers and parking sites ($m \in M$), $M = N \bigcup P_0$

    $C$

    set of clusters ($c \in C$), $\vert C \vert$ = $\vert N \vert$

    $L$

    set of service workers in any cluster ($l \in L$)

    $Q$

    sufficiently large number to exclude certain combinations of customers, parking sites and service workers

    $wt_{pn}$

    walking time from parking site $p$ to customer $n$

    $\alpha_{pn}$

    earliest starting time of a customer minus $wt_{pn}$

    $\beta_{pn}$

    latest starting time of a customer minus $wt_{pn}$

    $st_{np}$

    service time of customer $n$ plus return time to parking site $p$

    $d_n$

    demand of customer $n$

    $\text{cap}$

    truck capacity

    $\eta \in \{1,0\}$

    parameter controlling emphasis on minimizing the number of clusters versus the makespan

  • Decision Variables
    • $x_{cp}=\begin{cases} 1, \text{if cluster }c\text{ uses parking site }p\\ 0, \text{otherwise} \end{cases}$
    • $y_{cpn}=\begin{cases} 1, \text{if customer }n\text{ is in cluster }c\text{ with parking site } p\\ 0, \text{otherwise} \end{cases}$
    • $v_{nn'}^{lc}=\begin{cases} 1, \text{if service worker }l\text{ walks from }n\text{ to }n'\text{ in cluster }c\\ 0, \text{otherwise} \end{cases}$

    $\delta_n$

    actual starting time at a customer $n$ which is a real number with a lower bound of zero

    $\overline{\xi_c}$

    actual finishing time of cluster $c$ (time when a truck leaves) which is a real number with a lower bound of zero

    $\underline{\xi_c}$

    actual starting time of cluster $c$ (time when truck arrives) which is a real number with a lower bound of zero

  • $$ \min z = \eta \sum_{c \in C} (\overline{\xi_c} - \underline{\xi_c}) + (1-\eta) \sum_{c \in C}\sum_{p \in P0}x_{cp} $$

    s.t.

    $$ \overline{\xi_c} - \underline{\xi_c} \geq 0\\ \sum_{p \in P_0} x_{cp} \leq 1, \forall c \in C\\ \sum_{n \in N} y_{cpn} \cdot d_n \leq \text{cap} \cdot x_{cp}, \forall p \in P_0, \forall c \in C\\ \sum_{c \in C}\sum_{p \in P0} y_{cpn} = 1, \forall n \in N\\ y_{cpn} \leq x_{cp}, \forall n \in N, p \in P_0, \forall c \in C\\ x_{cp} \leq \sum_{n \in N} y_{cpn}, \forall p \in P0, \forall c \in C\\ \sum_{l \in L} \sum_{\substack{n' \in M \\ n' \neq n}} v_{nn'}^{lc} \leq \sum_{p \in P_0} y_{cpn}, \forall c \in C, \forall n \in N\\ \sum_{n'' \in M} v_{n''n}^{lc} = \sum_{n' \in M} v_{nn'}^{lc}, \forall n \in N, \forall c \in C, \forall l \in L\\ \sum_{c \in C}\sum_{l \in L}\sum_{\substack{n' \in M \\ n' \neq n}} v_{nn'}^{lc} = 1, \forall n \in N\\ \delta_n \geq \alpha_{pn} \cdot y_{cpn} - Q \cdot (1-y_{cpn}),\forall n \in N, \forall p \in P0, \forall c \in C\\ \delta_n \leq \beta_{pn} \cdot y_{cpn} + Q \cdot (1-y_{cpn}),\forall n \in N, \forall p \in P0, \forall c \in C\\ \delta_n \geq \delta_{n'} + wt_{pn'} + st_{pn'} -Q \cdot (1-v_{n'n}^{lc}) - Q \cdot (1-y_{cpn}), \forall n \in N, \forall p \in P0, \forall l \in L, \forall n' \in M, \forall c \in C\\ \underline{\xi_c} \leq \delta_n + Q \cdot (1-y_{cpn}), \forall n \in N, p \in P_0, \forall c \in C\\ \overline{\xi_c} \geq \delta_n + (wt_{pn} + st_{pn}) \cdot y_{cpn} - Q \cdot (1-y_{cpn}), \forall n \in N, p \in P_0, \forall c \in C\\ $$

Summary and Outlook