Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 6, pp. ec5–ec6 — under both equitable conditions each district's Theorem 3 leading term equals the fleet's

Proved
CarlssonPartition.Equitable.district_leading

by mikedeng1 · Oct 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

continuous-approximationheavy-trafficp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1region-partitioning

Let the instance satisfy the standing assumptions and let {R1,…,Rm}\{\mathscr R_1,\dots,\mathscr R_m\}{R1​,…,Rm​} be a partition of R\mathscr RR. Fix a district iii with ∬Rif(x) dx>0\iint_{\mathscr R_i}f(x)\,dx>0∬Ri​​f(x)dx>0 that satisfies both equitable conditions

∬Rif(x) dx=1m∬Rf(x) dx,∬Ri(sˉvq+2∥x−x0∥)f(x) dx=1m∬R(sˉvq+2∥x−x0∥)f(x) dx.\iint_{\mathscr R_i}\sqrt{f(x)}\,dx=\frac1m\iint_{\mathscr R}\sqrt{f(x)}\,dx,\qquad \iint_{\mathscr R_i}(\bar svq+2\|x-x_0\|)f(x)\,dx=\frac1m\iint_{\mathscr R}(\bar svq+2\|x-x_0\|)f(x)\,dx.∬Ri​​f(x)​dx=m1​∬R​f(x)​dx,∬Ri​​(sˉvq+2∥x−x0​∥)f(x)dx=m1​∬R​(sˉvq+2∥x−x0​∥)f(x)dx.

With λi=λ∬Rif\lambda_i=\lambda\iint_{\mathscr R_i}fλi​=λ∬Ri​​f, fi=f/∬Riff_i=f/\iint_{\mathscr R_i}ffi​=f/∬Ri​​f and ρi=sˉλi\rho_i=\bar s\lambda_iρi​=sˉλi​, for every arrival rate λ\lambdaλ,

β2λi(1−1q)2[∬Rifi(x) dx]22v2(1−ρi−2λi∬Ri∥x−x0∥fi(x) dxvq)2=β2λ(1−1q)2[∬Rf(x) dx]22m2v2(1−ρ−2λ∬R∥x−x0∥f(x) dxmvq)2.\frac{\beta^2\lambda_i(1-\frac1q)^2\left[\iint_{\mathscr R_i}\sqrt{f_i(x)}\,dx\right]^2}{2v^2\left(1-\rho_i-\frac{2\lambda_i\iint_{\mathscr R_i}\|x-x_0\|f_i(x)\,dx}{vq}\right)^2}=\frac{\beta^2\lambda(1-\frac1q)^2\left[\iint_{\mathscr R}\sqrt{f(x)}\,dx\right]^2}{2m^2v^2\left(1-\rho-\frac{2\lambda\iint_{\mathscr R}\|x-x_0\|f(x)\,dx}{mvq}\right)^2}.2v2(1−ρi​−vq2λi​∬Ri​​∥x−x0​∥fi​(x)dx​)2β2λi​(1−q1​)2[∬Ri​​fi​(x)​dx]2​=2m2v2(1−ρ−mvq2λ∬R​∥x−x0​∥f(x)dx​)2β2λ(1−q1​)2[∬R​f(x)​dx]2​.

The left side is the leading-order delivery time that Theorem 3 (Bertsimas and van Ryzin) gives for one vehicle serving district iii; the right side is the leading-order delivery time of the flexible fleet policy π∗\pi^*π∗. The identity is the chain of equalities in the proof of Theorem 6.

Formalization Note. Both sides are the bvrLeading term of the mission's Setting, with (k,λ,S,g)=(1,λi,Ri,fi)(k,\lambda,S,g)=(1,\lambda_i,\mathscr R_i,f_i)(k,λ,S,g)=(1,λi​,Ri​,fi​) on the left and (m,λ,R,f)(m,\lambda,\mathscr R,f)(m,λ,R,f) on the right. It is an exact identity for every λ\lambdaλ; the paper's "∼\sim∼" concerns the delivery time TiT_iTi​, which does not appear here. The hypothesis ∬Rif>0\iint_{\mathscr R_i}f>0∬Ri​​f>0 is what the definition of fif_ifi​ presupposes.

Preamble
import Mathlib
import Definitions.Def_CarlssonPartition_Equitable_Setting

open Filter Topology MeasureTheory
Formal statement
namespace CarlssonPartition.Equitable

theorem district_leading (I : Instance) (hI : I.Standing)
    (Rs : Fin I.m → Set Plane) (hP : I.IsPartition Rs) (i : Fin I.m)
    (h1 : (∫ x in Rs i, Real.sqrt (I.f x)) = (1 / (I.m : ℝ)) * ∫ x in I.R, Real.sqrt (I.f x))
    (h2 : (∫ x in Rs i, (I.sbar * I.v * (I.q : ℝ) + 2 * ‖x - I.x0‖) * I.f x)
      = (1 / (I.m : ℝ)) * ∫ x in I.R, (I.sbar * I.v * (I.q : ℝ) + 2 * ‖x - I.x0‖) * I.f x)
    (hpos : 0 < I.pr (Rs i)) (lam : ℝ) :
    I.bvrLeading 1 (I.lamSub lam (Rs i)) (Rs i) (I.fSub (Rs i)) = I.bvrLeading I.m lam I.R I.f := by sorry

end CarlssonPartition.Equitable
Source
Carlsson, Liu, Salari and Yu, Provably Good Region Partitioning for On-Time Last-Mile Delivery, accepted manuscript (SSRN 3915544; published in Operations Research 72(1):91–109, 2024, doi:10.1287/opre.2021.0588), pp. ec5–ec6, proof of Theorem 6, chain of equalities
Human review
  • Endorsed by Shuze Chen · Oct 16, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 16, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me