25 Cyclic Rental Fleet and Repair Planning

Source and adaptation

Based on Car rental 1, Section 12.25 of Williams (2013). New three-depot, three-day cyclic instance with one-day rentals, deterministic return fractions, and a repair-state balance. The results below solve the stated instance and are not presented as the numerical answer to an unmodified textbook problem.

25.1 Problem Statement

Three depots A,B,C rent one-day vehicles in a repeating three-day cycle. Rental demand caps by day (A,B,C) are (15,12,10), (10,18,12), (12,10,18). Each rental contributes 25 USD before repair, transfer, and fleet costs. Return fractions from A are (0.7,0.2,0.1), from B (0.2,0.6,0.2), and from C (0.1,0.2,0.7). Ten percent of returns are damaged; 90% are immediately usable next morning. Damaged cars enter a separate queue and can only start repair after arrival. Repairs take one day and cost 2 USD/car, with daily depot capacities (2,1,1). Undamaged transfers take one day and cost 4 USD between A/B or B/C and 6 USD between A/C. At each morning, choose rentals, transfers, and repairs from the stocks then available. Fleet ownership costs 4 USD/car/day. Choose steady-state stocks and operations to maximize cycle profit. Fractional expected vehicle counts are allowed; no rounding is claimed to preserve feasibility.

25.1.1 Rental opportunities

Day	A	B	C
1	15	12	10
2	10	18	12
3	12	10	18

25.1.2 Return fractions

Origin	Return to A	Return to B	Return to C
A	0.7	0.2	0.1
B	0.2	0.6	0.2
C	0.1	0.2	0.7

25.2 Model Formulation

Morning usable and damaged stocks are \(s_{it},d_{it}\ge0\). Rentals \(r_{it}\), repairs \(v_{it}\), and transfers \(f_{ijt}\) are nonnegative. For cyclic successor \(t^+\),

\[r_{it}+\sum_{j\ne i}f_{ijt}\le s_{it},\quad v_{it}\le d_{it},\quad v_{it}\le C_i,\] \[s_{i,t^+}=s_{it}-r_{it}-\sum_jf_{ijt}+\sum_jf_{jit}+0.9\sum_jP_{ji}r_{jt}+v_{it},\] \[d_{i,t^+}=d_{it}-v_{it}+0.1\sum_jP_{ji}r_{jt}.\]

Demand bounds apply to rentals. Fleet size \(N=\sum_i(s_{i0}+d_{i0})\) is constant under the balances. Maximize \(25\sum r-2\sum v-\sum c_{ij}f_{ijt}-12N\). Repair output and transfer arrivals become usable the next morning. The model is an LP for expected fleet flows.

All decision variables and units refer to the problem statement above. Continuous variables are nonnegative unless explicitly stated otherwise; binary and integer domains are specified in the equations and code.

25.3 Pyomo Implementation

The following Python implementation uses Pyomo and HiGHS. Run from the workbook root so that the models package and shared helpers are importable. The shared solver and audit functions check optimal termination before loading values, then verify every active constraint, variable bound, and integer domain. Any imported earlier-chapter model supplies the data and balances already explained there.

The full source is problem25.py. To solve and print this problem independently:

~/.venvs/optim/bin/python -m models.common 25

import pyomo.environ as pyo
from models.common import frame

DEMAND = [[15, 12, 10], [10, 18, 12], [12, 10, 18]]
P = [[0.7, 0.2, 0.1], [0.2, 0.6, 0.2], [0.1, 0.2, 0.7]]
CAP = [2, 1, 1]


def build():
    m = pyo.ConcreteModel()
    m.I = pyo.RangeSet(0, 2)
    m.T = pyo.RangeSet(0, 2)
    arcs = [(i, j, t) for i in m.I for j in m.I if i != j for t in m.T]
    m.s = pyo.Var(m.I, m.T, domain=pyo.NonNegativeReals)
    m.d = pyo.Var(m.I, m.T, domain=pyo.NonNegativeReals)
    m.r = pyo.Var(m.I, m.T, domain=pyo.NonNegativeReals)
    m.v = pyo.Var(m.I, m.T, domain=pyo.NonNegativeReals)
    m.f = pyo.Var(arcs, domain=pyo.NonNegativeReals)
    m.c = pyo.ConstraintList()
    for i in m.I:
        for t in m.T:
            incoming = sum(P[j][i] * m.r[j, t] for j in m.I)
            outgoing = sum(m.f[i, j, t] for j in m.I if j != i)
            inbound = sum(m.f[j, i, t] for j in m.I if j != i)
            m.c.add(m.r[i, t] + outgoing <= m.s[i, t])
            m.c.add(m.r[i, t] <= DEMAND[t][i])
            m.c.add(m.v[i, t] <= m.d[i, t])
            m.c.add(
                m.s[i, (t + 1) % 3]
                == m.s[i, t]
                - m.r[i, t]
                - outgoing
                + inbound
                + 0.9 * incoming
                + m.v[i, t]
            )
            m.c.add(m.d[i, (t + 1) % 3] == m.d[i, t] - m.v[i, t] + 0.1 * incoming)
    m.repaircap = pyo.Constraint(m.I, m.T, rule=lambda m, i, t: m.v[i, t] <= CAP[i])
    m.fleet = pyo.Expression(expr=sum(m.s[i, 0] + m.d[i, 0] for i in m.I))
    m.obj = pyo.Objective(
        expr=25 * sum(m.r[i, t] for i in m.I for t in m.T)
        - 2 * sum(m.v[i, t] for i in m.I for t in m.T)
        - sum((4 if abs(i - j) == 1 else 6) * m.f[i, j, t] for i, j, t in arcs)
        - 12 * m.fleet,
        sense=pyo.maximize,
    )
    return m


def check(m):
    for t in m.T:
        assert (
            abs(sum(pyo.value(m.s[i, t] + m.d[i, t]) for i in m.I) - pyo.value(m.fleet))
            < 1e-6
        )
    assert (
        abs(sum(pyo.value(m.v[i, t] - 0.1 * m.r[i, t]) for i in m.I for t in m.T))
        < 1e-6
    )


def tables(m):
    return {
        "fleet_plan": frame(
            [
                [
                    t + 1,
                    "ABC"[i],
                    *[pyo.value(getattr(m, k)[i, t]) for k in ["s", "d", "r", "v"]],
                ]
                for t in m.T
                for i in m.I
            ],
            ["Day", "Depot", "Usable stock", "Damaged stock", "Rentals", "Repairs"],
        ),
        "transfers": frame(
            [
                [t + 1, "ABC"[i], "ABC"[j], pyo.value(m.f[i, j, t])]
                for i, j, t in m.f
                if pyo.value(m.f[i, j, t]) > 1e-6
            ],
            ["Day", "From", "To", "Vehicles"],
        ),
    }


def plot(m):
    return (
        ["Day 1", "Day 2", "Day 3"],
        [sum(pyo.value(m.r[i, t]) for i in m.I) for t in m.T],
        "Vehicles rented (expected count)",
    )

# Solve, audit constraints, and run domain-specific checks.
from models.common import solve, audit
model = solve(build())
audit(model)
check(model)
for name, result_table in tables(model).items():
    print(name)
    print(result_table.to_string(index=False))

25.4 Optimal Solution

The solver reports optimal termination. The objective is 1,885.664844 USD per three-day cycle (maximize). The largest violation across active constraints, variable bounds, and integer domains is 3.55e-15 in the corresponding model units. The problem-specific checks also pass. These checks establish numerical consistency with the stated model, not the validity of its assumptions for a real facility.

25.4.1 Fleet plan

Day	Depot	Usable stock	Damaged stock	Rentals	Repairs
1	A	15	1.0991	15	0.4317
1	B	9.2753	1	9.2753	1
1	C	9.7026	1	9.7026	1
2	A	12.4245	2	10	2
2	B	10.4551	1.0506	10.4551	1
2	C	10.1322	1.0147	10.1322	1
3	A	13.5183	1.0104	12	1.0104
3	B	10.2696	1.0805	8.059	1
3	C	10.1652	1.033	9.7968	1

25.4.2 Transfers

Day	From	To	Vehicles
3	B	A	2.2105
3	C	A	0.3684

Figure 25.1: Selected quantities from the verified optimal solution. Units are stated on the axis.

Tables round numerical values for reading; feasibility checks use the original solver values. Multiple optimal decisions may exist. Machine-readable result records the solver status and package versions. Figure-generation code is in figures/workbook.py.

25.5 Brief Discussion

The steady-state fleet contains 37.08 expected vehicles and supports 94.42 rentals per cycle. Fractional fleet counts reflect the expected-flow approximation.

Repair queues consume fleet capital as well as repair capacity. Ignoring the damaged stock would make cars reappear without a delay. Cyclic boundary conditions remove a privileged start day but assume the demand pattern repeats. Experiment: double one depot’s repair capacity and measure the value before adding a fixed investment charge.