pith. sign in

arxiv: 1906.08844 · v1 · pith:ELXLQRSWnew · submitted 2019-06-20 · 🧮 math.OC · cs.NI

Service Network Design Problem with Capacity-Demand Balancing

Yusuf Secerdin , Murat Erkoc This is my paper

Pith reviewed 2026-05-25 19:11 UTC · model grok-4.3

classification 🧮 math.OC cs.NI
keywords service network designmulti-period planningcapacity balancingvalid inequalitiesheuristic algorithmoutsourcingasset managementdemand dispersion
0
0 comments X

The pith

A multi-period service network design model incorporates demand dispersion with penalties, temporary asset leasing, and outsourcing to minimize costs when demand exceeds capacity in some periods.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper builds a model for service network design over multiple periods in which carriers face temporary excess demand even if average yearly demand fits their assets. Carriers can respond by spreading demand across time at a penalty cost, leasing extra assets short-term, or outsourcing to third parties. The formulation jointly optimizes asset scheduling, outsourcing choices, and commodity routing on the designed network. Valid inequalities tighten the mathematical program, and a custom multi-phase dedicate-merge-and-mix algorithm finds high-quality solutions quickly for instances too large for commercial solvers. A sympathetic reader cares because seasonal spikes are common in freight networks, and the approach shows how to plan without assuming capacity always matches demand.

Core claim

The paper claims that an arc-based formulation of the capacity-demand balancing service network design problem, augmented with valid inequalities and solved via the dedicate-merge-and-mix algorithm, enables carriers to select and schedule their home fleet, choose third-party services, and route flows so as to minimize total operational costs when demand exceeds capacity in certain periods.

What carries the argument

Arc-based mixed-integer formulation with valid inequalities together with the multi-phase dedicate-merge-and-mix (DMaM) algorithm.

If this is right

  • The valid inequalities produce tighter lower bounds than the basic formulation.
  • One set of valid inequalities reduces CPU time by 25 percent on medium instances that reach optimality within the time limit.
  • The DMaM algorithm obtains high-quality solutions for very large instances where a commercial solver cannot even start the branch-and-bound process due to memory limits.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same three-response structure could be tested on energy or telecommunications networks that also face time-varying capacity shortfalls.
  • Running DMaM on instances with correlated demand spikes across adjacent periods would reveal whether the algorithm remains effective when random-generation assumptions are relaxed.
  • Embedding the model inside a rolling-horizon planner would show how often re-optimization is needed when new demand forecasts arrive.

Load-bearing premise

The modeling premise that randomly generated instances represent real-world multi-period service networks and that the only realistic responses to excess demand are dispersion with penalty, temporary leasing, and outsourcing.

What would settle it

Solve the model on a carrier's actual historical demand and asset data, then compare the model's recommended mix of dispersion, leasing, and outsourcing against the carrier's observed decisions and realized costs during past excess-demand periods.

Figures

Figures reproduced from arXiv: 1906.08844 by Murat Erkoc, Yusuf Secerdin.

Figure 1
Figure 1. Figure 1: A sample time-space network with two assets. [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of 2-weeks anomaly in commodity flows. [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of close-range and mid-range networks on US regions. [PITH_FULL_IMAGE:figures/full_fig_p023_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of a long-range network on US map. [PITH_FULL_IMAGE:figures/full_fig_p024_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Some solutions for the multiple allocation problem. [PITH_FULL_IMAGE:figures/full_fig_p046_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Flowchart of the DMaM. 52 [PITH_FULL_IMAGE:figures/full_fig_p052_6.png] view at source ↗
read the original abstract

This paper addresses developing cost-effective strategies to respond to excessive demand in the service network design problem in a multi-period setting. The common assumption states that the capacity of freight carriers' assets is capable of handling all of the forecasted demand; however, we assume that there are certain periods such as holiday season in which excessive demand is observed. The demand strictly exceeds the carrier's capacity; even though, the average demand can be still fulfilled throughout the year. In this sense, we let the carrier has three options to respond to the demand: Dispersing the demand with a penalty, leasing additional asset(s) temporarily, and outsourcing some capacity. We propose a modeling and solution approach that jointly incorporates asset management and sizing, outsourcing (3PLs), and earliness/tardiness penalties. The objective is to minimize the overall operational costs by optimally selecting and scheduling the home fleet with respect to 'demand shifting' choices, selecting services from third parties, and routing the commodities on the designed network. We propose an arc-based formulation as well as valid inequalities and present a comprehensive computational study on the randomly generated instances. The formulations with valid inequalities (VIs) outperform the regular formulation in obtaining tighter lower bounds. One set of VIs can improve the CPU time elapsed by 25% on medium-instances that can be solved optimally within the time limit. Furthermore, we develop a custom multi-phase dedicate-merge-and-mix algorithm (DMaM) to solve CSSND problem with an emphasis of obtaining solutions as high-quality as possible practically in a short time in the real world. DMaM has a promising potential to obtain solutions especially for very large instances whereas the commercial solver cannot initialize the B&B algorithm due to excessive memory usage.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes an arc-based mixed-integer programming formulation for the multi-period capacity-demand balancing service network design (CSSND) problem. Carriers can respond to excess-demand periods via demand dispersion (with penalty), temporary asset leasing, or outsourcing. The authors derive valid inequalities to tighten the LP relaxation, report computational experiments on randomly generated instances showing improved lower bounds and up to 25% CPU-time reduction on medium instances, and present a multi-phase dedicate-merge-and-mix (DMaM) heuristic that produces feasible solutions on very large instances where CPLEX fails to start the branch-and-bound tree.

Significance. If the reported bound improvements and heuristic performance hold under reproducible conditions, the work supplies a concrete modeling framework and algorithmic tools for integrating asset sizing, 3PL selection, and demand-shifting decisions in service networks that experience seasonal overloads. The valid inequalities and DMaM algorithm constitute reusable methodological contributions for large-scale network design MIPs.

major comments (2)
  1. [Section 5] Computational study (Section 5): all performance claims (tighter bounds, 25% CPU reduction on medium instances, DMaM quality on very large instances) rest exclusively on randomly generated instances. The manuscript supplies neither the instance generator, the precise sampling distributions for demand spikes and cost coefficients, nor any real carrier data set. This directly undermines reproducibility and the practical-support claim made in the abstract and introduction.
  2. [Section 2] Problem definition (Section 2): the modeling premise that the only realistic responses to excess demand are dispersion-with-penalty, temporary leasing, and outsourcing is stated without supporting references, sensitivity analysis on the penalty/lease/outsourcing cost coefficients, or comparison to alternative responses (e.g., dynamic pricing or inventory carry-over). Because the objective and feasible region are built directly on these three options, the premise is load-bearing for the entire formulation.
minor comments (2)
  1. [Section 5] Tables in the computational section should report the number of instances per size class, the fraction solved to optimality, and standard deviations on CPU times so that the 25% improvement figure can be statistically interpreted.
  2. [Section 6] The description of the DMaM phases would benefit from a compact pseudocode listing or flowchart to clarify the dedicate, merge, and mix steps.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback. Below we respond point-by-point to the two major comments. We agree that greater transparency on instance generation and additional analysis on cost parameters would strengthen the paper and will incorporate these elements in a revision.

read point-by-point responses

  1. Referee: [Section 5] Computational study (Section 5): all performance claims (tighter bounds, 25% CPU reduction on medium instances, DMaM quality on very large instances) rest exclusively on randomly generated instances. The manuscript supplies neither the instance generator, the precise sampling distributions for demand spikes and cost coefficients, nor any real carrier data set. This directly undermines reproducibility and the practical-support claim made in the abstract and introduction.

    Authors: We acknowledge that the experiments rely on randomly generated instances and that the current manuscript does not include the generator code or explicit sampling distributions. In the revision we will add a detailed subsection describing the instance-generation procedure, including the probability distributions and parameters used for demand spikes and all cost coefficients. Real-world carrier data sets are typically proprietary; our synthetic instances were constructed to reproduce the seasonal overload patterns described in Section 2 and the abstract. We believe the added generation details will satisfy reproducibility requirements while preserving the modeling contribution. revision: partial

  2. Referee: [Section 2] Problem definition (Section 2): the modeling premise that the only realistic responses to excess demand are dispersion-with-penalty, temporary leasing, and outsourcing is stated without supporting references, sensitivity analysis on the penalty/lease/outsourcing cost coefficients, or comparison to alternative responses (e.g., dynamic pricing or inventory carry-over). Because the objective and feasible region are built directly on these three options, the premise is load-bearing for the entire formulation.

    Authors: The three response mechanisms reflect common industry practice for handling temporary capacity shortfalls in freight networks. We will insert supporting references from the service-network-design and 3PL literature in the revision. We also agree that a sensitivity study on the penalty, leasing, and outsourcing cost coefficients is warranted and will add the corresponding experiments. Dynamic pricing and inventory carry-over would require an entirely different decision space (pricing variables or multi-period inventory balance constraints) that lies outside the scope of the present arc-based network-design model; we will clarify this modeling boundary in the revised introduction. revision: partial

Circularity Check

0 steps flagged

No circularity: standard MIP formulation and empirical evaluation on random instances

full rationale

The paper presents an arc-based MIP formulation for a multi-period service network design problem, valid inequalities, and a heuristic (DMaM). The objective directly minimizes explicitly defined cost terms (asset management, outsourcing, penalties). No equations reduce to fitted parameters renamed as predictions, no self-citations are load-bearing for the central claims, and no uniqueness theorems or ansatzes are smuggled in. Performance results are reported on randomly generated instances; this is an empirical claim, not a derivation that collapses to its inputs by construction. The modeling premise is stated explicitly rather than derived circularly.

Axiom & Free-Parameter Ledger

2 free parameters · 1 axioms · 0 invented entities

The paper relies on standard domain assumptions from service network design and introduces no new postulated entities; cost coefficients are treated as exogenous inputs rather than fitted parameters.

free parameters (2)
  • earliness/tardiness penalty rates
    User-specified cost parameters that directly enter the objective and affect optimal routing and timing decisions.
  • leasing and outsourcing cost coefficients
    Input parameters representing temporary asset rental and 3PL rates that shape the capacity-balancing choices.
axioms (1)
  • domain assumption Demand exceeds carrier capacity only in selected periods while yearly average demand remains fulfillable
    Core problem setting stated in the abstract that defines when the three response options become active.

pith-pipeline@v0.9.0 · 5842 in / 1245 out tokens · 27836 ms · 2026-05-25T19:11:21.593355+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Designing new european rail freight services

    Andersen, J., and Christiansen, M. Designing new european rail freight services. Journal of the Operational Research Society 60 , 3 (2009), 348–360

    work page 2009

  2. [2]

    G., and Grønhaug, R

    Andersen, J., Christiansen, M., Crainic, T. G., and Grønhaug, R. Branch and price for service network design with asset management constraints. Transportation Science 45, 1 (2011), 33–49

    work page 2011

  3. [3]

    Service network design with asset management: Formulations and comparative analyses

    Andersen, J., Crainic, T., and Christiansen, M. Service network design with asset management: Formulations and comparative analyses. Transportation Research Part C: Emerging Technologies 17, 2 (2009), 197–207

    work page 2009

  4. [4]

    Service network design with man- agement and coordination of multiple fleets

    Andersen, J., Crainic, T., and Christiansen, M. Service network design with man- agement and coordination of multiple fleets. European Journal of Operational Research 193, 2 (2009), 377–389

    work page 2009

  5. [5]

    Composite variable formulation for express shipment service network design

    Armacost, A., Barnhart, C., and Ware, K. Composite variable formulation for express shipment service network design. Transportation Science 36 (2002), 1–20. 58

    work page 2002

  6. [6]

    Bai, R., Kendall, G., Qu, R., and Atkin, J. A. Tabu assisted guided local search approaches for freight service network design. Information Sciences 189 (2012), 266–281

    work page 2012

  7. [7]

    R., Subramanian, N., and Cartlidge, J

    Bai, R., Woodward, J. R., Subramanian, N., and Cartlidge, J. Optimisation of transportation service network using κ-node large neighbourhood search. Computers & Operations Research 89 (2018), 193–205

    work page 2018

  8. [8]

    L., and Mirchandani, P

    Balakrishnan, A., Magnanti, T. L., and Mirchandani, P. Network design. Anno- tated bibliographies in combinatorial optimization (1997), 311–334

    work page 1997

  9. [9]

    Network design for express shipment delivery

    Barnhart, C., Krishnan, N., Kim, D., and Ware, K. Network design for express shipment delivery. Computational Optimization and Applications 21 , 3 (2002), 239–262

    work page 2002

  10. [10]

    Barnhart, C., and Schneur, R. R. Air network design for express shipment service. Operations Research 44, 6 (1996), 852–863

    work page 1996

  11. [11]

    G.Minimizing greenhouse gas emissions in in- termodal freight transport: an application to rail service design

    Bauer, J., Bektas ¸, T., and Crainic, T. G.Minimizing greenhouse gas emissions in in- termodal freight transport: an application to rail service design. Journal of the Operational Research Society 61, 3 (2010), 530–542

    work page 2010

  12. [12]

    Chouman, M., and Crainic, T. G. Cutting-plane matheuristic for service network design with design-balanced requirements. Transportation Science 49, 1 (2015), 99–113

    work page 2015

  13. [13]

    Crainic, T. G. Service network design in freight transportation. European Journal of Operational Research 122, 2 (2000), 272–288

    work page 2000

  14. [14]

    G., Hewitt, M., Toulouse, M., and Vu, D

    Crainic, T. G., Hewitt, M., Toulouse, M., and Vu, D. M.Scheduled service network design with resource acquisition and management. EURO Journal on Transportation and Logistics (2016), 1–33

    work page 2016

  15. [15]

    G., Hewitt, M., Toulouse, M., and Vu, D

    Crainic, T. G., Hewitt, M., Toulouse, M., and Vu, D. M. Service network design with resource constraints. Transportation Science 50, 4 (2016), 1380–1393

    work page 2016

  16. [16]

    G., and Kim, K

    Crainic, T. G., and Kim, K. H. Intermodal transportation. Handbooks in operations research and management science 14 (2007), 467–537

    work page 2007

  17. [17]

    G., and Sgalambro, A

    Crainic, T. G., and Sgalambro, A. Service network design models for two-tier city logistics. Optimization Letters 8 , 4 (2014), 1375–1387

    work page 2014

  18. [18]

    Annual Report 2016

    FedEx, C. Annual Report 2016. Availabe at: http://investors.fedex.com/ financial-information/annual-reports/default.aspx, 2017. Online; accessed 3- January-2018. 59

    work page 2016

  19. [19]

    Scheduling drivers and routing shipments in tandem

    Hewitt, M. Scheduling drivers and routing shipments in tandem. In IIE Annual Confer- ence. Proceedings (2010), Institute of Industrial and Systems Engineers (IISE), p. 1

    work page 2010

  20. [20]

    Multimodal express package delivery: A service network design application

    Kim, D., Barnhart, C., Ware, K., and Reinhardt, G. Multimodal express package delivery: A service network design application. Transportation Science 33 (1999), 391–407

    work page 1999

  21. [21]

    Lai, M., and Lo, H. K. Ferry service network design: optimal fleet size, routing, and scheduling. Transportation Research Part A: Policy and Practice 38 , 4 (2004), 305–328

    work page 2004

  22. [22]

    Design-balanced capacitated multicommodity network design with heterogeneous assets

    Li, X., Wei, K., Aneja, Y., and Tian, P. Design-balanced capacitated multicommodity network design with heterogeneous assets. Omega 67 (2017), 145–159

    work page 2017

  23. [23]

    P., Tian, P., and Cui, Y

    Li, X., Wei, K., Aneja, Y. P., Tian, P., and Cui, Y. Matheuristics for the single- path design-balanced service network design problem. Computers & Operations Research 77 (2017), 141–153

    work page 2017

  24. [24]

    L., and Wong, R

    Magnanti, T. L., and Wong, R. T. Network design and transportation planning: Models and algorithms. Transportation science 18, 1 (1984), 1–55

    work page 1984

  25. [25]

    B., Crainic, T

    Pedersen, M. B., Crainic, T. G., and Madsen, O. B. Models and tabu search metaheuristics for service network design with asset-balance requirements. Transportation Science 43, 2 (2009), 158–177

    work page 2009

  26. [26]

    P., Nuijten, W., Van Woensel, T., and Raoufi, R

    SteadieSeifi, M., Dellaert, N. P., Nuijten, W., Van Woensel, T., and Raoufi, R. Multimodal freight transportation planning: A literature review. European journal of operational research 233, 1 (2014), 1–15

    work page 2014

  27. [27]

    A decomposition scheme for large-scale service network design with asset management

    Teypaz, N., Schrenk, S., and Cung, V.-D. A decomposition scheme for large-scale service network design with asset management. Transportation Research Part E: Logistics and Transportation Review 46, 1 (2010), 156–170

    work page 2010

  28. [28]

    M., Crainic, T

    Vu, D. M., Crainic, T. G., and Toulouse, M. A three-phase matheuristic for capaci- tated multi-commodity fixed-cost network design with design-balance constraints. Journal of heuristics 19 , 5 (2013), 757–795

    work page 2013

  29. [29]

    William, B. C. JOC Top 50 LTL Carriers: Small carriers, fast growth. Available at: https://www.joc.com/trucking-logistics/ltl-shipping/ joc-top-50-ltl-carriers-small-carriers-fast-growth_20170817.html , 2017. Online; accessed 3-January-2018. 60

    work page 2017

  30. [30]

    Annual Report 2016

    XPO Logistics, I. Annual Report 2016. Availabe at: http://investors.xpo.com/ phoenix.zhtml?c=204615&p=irol-reportsannual_pf, 2017. Online; accessed 3-January- 2018

    work page 2016

  31. [31]

    G., and Gendreau, M

    Zhu, E., Crainic, T. G., and Gendreau, M. Scheduled service network design for freight rail transportation. Operations research 62, 2 (2014), 383–400. 61

    work page 2014