The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem

Antonio Lauerbach; Kendra Reiter; Marie Schmidt

arxiv: 2409.15192 · v2 · submitted 2024-09-23 · 💻 cs.CC

The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem

Antonio Lauerbach , Kendra Reiter , Marie Schmidt This is my paper

Pith reviewed 2026-05-23 20:28 UTC · model grok-4.3

classification 💻 cs.CC

keywords line-based Dial-a-Ridecomputational complexityNP-hardnessparameterized algorithmsturn minimizationpassenger transportationvehicle routing

0 comments

The pith

Instance parameters divide the line-based Dial-a-Ride problem and its minimum-turn variant into polynomial and NP-hard cases.

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

The paper establishes the boundary between polynomially solvable and NP-hard instances of the line-based Dial-a-Ride problem, which maximizes the number of transported passenger requests along a fixed sequence of stops with shortcut options, and of the related MinTurn problem that seeks the minimum number of turns in an optimal solution. It supplies parameterized algorithms that solve both problems when the relevant parameters are fixed. A sympathetic reader would care because these results clarify when exact solutions for consolidating shared-vehicle trips can be computed efficiently and when they cannot. The classification rests on instance parameters and characteristics that together produce the stated complexity partition.

Core claim

Based on a number of instance parameters and characteristics, the boundary between polynomially solvable and NP-hard instances is stated for both the LiDARP and the MinTurn problem, and parameterized algorithms are provided that solve both.

What carries the argument

Instance parameters and characteristics that classify the complexity of the LiDARP maximization problem and the MinTurn problem.

If this is right

When the parameters fall into the polynomial region, optimal LiDARP solutions and their minimum-turn versions can be computed in polynomial time.
When the parameters fall into the NP-hard region, no polynomial-time algorithm exists for either problem unless P equals NP.
The parameterized algorithms solve both problems exactly whenever the fixed parameters remain small.
The classification directly identifies which transportation-request instances admit efficient exact consolidation and which do not.

Where Pith is reading between the lines

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

The MinTurn objective could be combined with other routing criteria to produce smoother passenger itineraries without increasing computational cost in the polynomial cases.
Similar parameter-based classifications might separate easy and hard instances in related vehicle-routing problems that also allow shortcuts along a line.
Real-world dial-a-ride systems could use the parameters as a quick filter to decide whether to invoke an exact solver or switch to heuristics.

Load-bearing premise

The chosen instance parameters produce a clean, exhaustive partition into polynomial and NP-hard cases with no overlooked exceptions.

What would settle it

An instance whose parameters predict polynomial-time solvability yet requires super-polynomial time for an optimal solution, or whose parameters predict NP-hardness yet admits a polynomial-time algorithm, would falsify the boundary.

Figures

Figures reproduced from arXiv: 2409.15192 by Antonio Lauerbach, Kendra Reiter, Marie Schmidt.

**Figure 1.** Figure 1: A MinTurn instance constructed from a 3-Partition instance with m = 3 and T = 5, as well as s1 = 3 and sn = 2. The arrows represent the requests, with the white tipped arrows being value requests. all requests, each ascending subroute must thus contain exactly one filter request. It follows that each ascending subroute must also contain exactly one promise request, since promise and filter request overlap.… view at source ↗

**Figure 2.** Figure 2: The layout of the stops constructed for a 3-Partition instance. The line is the continuous path, while shortcuts are represented by (dotted) lines. The distances between neighboring stops are given by (blue) labels, with the exception of distances of 1, which are omitted. The line starts at stop hs then contains (in the order in which they are listed here) a sequence of stops h j f for j ∈ [m], a stop h e … view at source ↗

**Figure 3.** Figure 3: A tour serving all requests of an instance constructed in the reduction from 3-Partition to the MinTurn problem with m = 2. The value requests in PV, represented by (blue) dashed arrows, are served in the intervals between the separator requests, represented by (red) solid arrows. The subtours used to return from serving a request are represented by lighter lines. Assume that there is a feasible tour that… view at source ↗

read the original abstract

Dial-a-Ride problems have been proposed to model the challenge to consolidate passenger transportation requests with a fleet of shared vehicles. The line-based Dial-a-Ride problem (LiDARP) is a variant where the passengers are transported along a fixed sequence of stops, with the option of taking shortcuts. In this paper we consider the LiDARP with the objective function to maximize the number of transported requests. We investigate the complexity of two optimization problems: the LiDARP, and the problem to determine the minimum number of turns needed in an optimal LiDARP solution, called the MinTurn problem. Based on a number of instance parameters and characteristics, we are able to state the boundary between polynomially solvable and NP-hard instances for both problems. Furthermore, we provide parameterized algorithms that are able to solve both the LiDARP and MinTurn problem.

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.

Desk Editor's Note private letter to a colleague

The paper maps a clean P/NP-hard boundary for LiDARP and MinTurn using instance parameters and supplies FPT algorithms for the hard cases.

read the letter

The main thing to know is that this paper identifies a set of instance parameters that split LiDARP and the MinTurn problem into polynomial-time solvable cases and NP-hard cases, then gives parameterized algorithms that work when the parameters are small. That is the core contribution, and it is stated directly in the abstract without obvious internal contradictions or circular claims. The stress-test note is right that nothing in the provided description flags a load-bearing gap in the partition itself. The work is standard complexity classification for a routing variant, but it is executed on a concrete problem with fixed stops and optional shortcuts, which makes the boundaries potentially usable for algorithm designers in operations research. The authors earn credit for stating both the decision boundary and the FPT results in one package rather than leaving one side dangling. The parameters appear to produce an exhaustive split, which is the kind of outcome that justifies the effort. Soft spots are limited. The abstract does not list the exact parameters, so it is impossible to judge from the summary alone whether they are the most natural ones or whether some edge cases slip through; the full paper would need to show the reductions and the DP recurrences explicitly. That is a normal requirement rather than a flaw. No evidence of invented entities or unfalsifiable claims appears. This paper is for researchers who work on parameterized complexity of vehicle routing or dial-a-ride variants. A reader already familiar with the broader dial-a-ride literature will get the most value from the specific boundaries. It is coherent on its own terms and the results are specific enough to be checked, so it deserves a serious referee even if the final verdict after review is that the parameters need tightening. I would send it to peer review.

Referee Report

0 major / 2 minor

Summary. The paper studies the line-based Dial-a-Ride problem (LiDARP) with the objective of maximizing the number of transported passenger requests along a fixed sequence of stops (with shortcuts allowed), as well as the MinTurn problem of computing the minimum number of turns required in an optimal LiDARP solution. It claims to delineate, via a collection of instance parameters and characteristics, the exact boundary separating polynomially solvable cases from NP-hard cases for both problems, and to supply parameterized algorithms that solve the problems under those parameters.

Significance. If the claimed P/NP-hard partition and the parameterized algorithms are correct, the results supply a clean complexity map for a practically motivated variant of Dial-a-Ride, which can inform both algorithmic design and the choice of instance features in transportation consolidation problems. The explicit provision of FPT algorithms for the retained parameters is a concrete strength.

minor comments (2)

[Abstract] Abstract: the concrete instance parameters and characteristics that produce the stated P/NP-hard boundary are not enumerated, making it difficult for a reader to assess the scope of the classification without reading the full text.
The manuscript would benefit from an explicit statement (early in the introduction or in a dedicated section) of the precise parameter set used for the dichotomy, together with a short table summarizing which combinations yield polynomial time and which yield NP-hardness.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our work and the recommendation for minor revision. The provided summary accurately captures the paper's focus on delineating P vs. NP-hard boundaries for LiDARP and MinTurn via instance parameters and supplying parameterized algorithms.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper performs a standard complexity classification of the LiDARP and MinTurn problems, partitioning instances into polynomial and NP-hard cases via instance parameters and supplying FPT algorithms. No equations, fitted parameters, predictions, or self-citations appear in the provided abstract or description. Derivations consist of reductions and dynamic-programming recurrences whose correctness is independent of the target classification; the central claims do not reduce to their own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions from complexity theory; no free parameters, invented entities, or ad-hoc axioms are visible in the abstract.

axioms (1)

standard math Standard definitions of polynomial time, NP-hardness, and fixed-parameter tractability
Invoked to classify problems and design algorithms.

pith-pipeline@v0.9.0 · 5674 in / 1081 out tokens · 23960 ms · 2026-05-23T20:28:04.538955+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

[1]

Transportation Research Part C: Emerging Technologies19(5), 741–750 (2011).https://doi.org/10.1016/j.trc.2009.12.006

Archetti, C., Feillet, D., Gendreau, M., Grazia Speranza, M.: Complexity of the VRP and SDVRP. Transportation Research Part C: Emerging Technologies19(5), 741–750 (2011).https://doi.org/10.1016/j.trc.2009.12.006

work page doi:10.1016/j.trc.2009.12.006 2011
[2]

ACM Trans

Bjelde, A., Hackfeld, J., Disser, Y., Hansknecht, C., Lipmann, M., Meißner, J., Schlöter, M., Schewior, K., Stougie, L.: Tight bounds for online TSP on the line. ACM Trans. Algorithms17(1), 3:1–3:58 (2021).https://doi.org/10.1145/ 3422362

work page 2021
[3]

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979).https://doi.org/10.5555/574848

work page doi:10.5555/574848 1979
[4]

Gaul, D., Klamroth, K., Stiglmayr, M.: Event-based MILP models for ridepooling applications. Eur. J. Oper. Res.301(3), 1048–1063 (2022).https://doi.org/10. 1016/J.EJOR.2021.11.053

work page 2022
[5]

Information Pro- cessing Letters 86(2), 87–91 (2003).https://doi.org/10.1016/S0020-0190(02) 00474-X

Gaur, D.R., Gupta, A., Krishnamurti, R.: A 53-approximation algorithm for scheduling vehicles on a path with release and handling times. Information Pro- cessing Letters 86(2), 87–91 (2003).https://doi.org/10.1016/S0020-0190(02) 00474-X

work page doi:10.1016/s0020-0190(02 2003
[6]

Discrete Applied Math- ematics 81(1), 41–57 (Jan 1998)

Guan, D.J.: Routing a vehicle of capacity greater than one. Discrete Applied Math- ematics 81(1), 41–57 (Jan 1998). https://doi.org/10.1016/S0166-218X(97) 00074-7

work page doi:10.1016/s0166-218x(97 1998
[7]

In: Chen, B

Haugland, D., Ho, S.C.: Feasibility Testing for Dial-a-Ride Problems. In: Chen, B. (ed.) Algorithmic Aspects in Information and Management. pp. 170–179. Springer, Berlin, Heidelberg (2010).https://doi.org/10.1007/978-3-642-14355-7_18

work page doi:10.1007/978-3-642-14355-7_18 2010
[8]

Transporta- tion Research Part B: Methodological111, 395–421 (2018).https://doi.org/10

Ho, S.C., Szeto, W., Kuo, Y.H., Leung, J.M., Petering, M., Tou, T.W.: A survey of dial-a-ride problems: Literature review and recent developments. Transporta- tion Research Part B: Methodological111, 395–421 (2018).https://doi.org/10. 1016/j.trb.2018.02.001

work page 2018
[9]

Discrete Mathematics306(19), 2529–2571 (2006)

Hougardy, S.: Classes of perfect graphs. Discrete Mathematics306(19), 2529–2571 (2006). https://doi.org/10.1016/j.disc.2006.05.021, creation and Recre- ation: A Tribute to the Memory of Claude Berge

work page doi:10.1016/j.disc.2006.05.021 2006
[10]

Hua, Q., Wang, Y., Yu, D., Lau, F.C.M.: Dynamic programming based algorithms for set multicover and multiset multicover problems. Theor. Comput. Sci.411(26- 28), 2467–2474 (2010).https://doi.org/10.1016/J.TCS.2010.02.016

work page doi:10.1016/j.tcs.2010.02.016 2010
[11]

In: auf der Heide, F.M

Karuno, Y., Nagamochi, H.: A 2-approximation algorithm for the multi-vehicle scheduling problem on a path with release and handling times. In: auf der Heide, F.M. (ed.) Algorithms — ESA 2001. pp. 218–229. Springer Berlin Heidelberg, Berlin, Heidelberg (2001).https://doi.org/10.1016/S0166-218X(02)00596-6

work page doi:10.1016/s0166-218x(02)00596-6 2001
[12]

Networks 39(4), 203–209 (2002)

Karuno, Y., Nagamochi, H., Ibaraki, T.: Better approximation ratios for the single- vehicle scheduling problems on line-shaped networks. Networks 39(4), 203–209 (2002). https://doi.org/10.1002/net.10028

work page doi:10.1002/net.10028 2002
[13]

INFORMS J

de Paepe, W., Lenstra, J.K., Sgall, J., Sitters, R.A., Stougie, L.: Computer-aided complexity classification of dial-a-ride problems. INFORMS J. Comput. 16(2), 120–132 (2004).https://doi.org/10.1287/IJOC.1030.0052

work page doi:10.1287/ijoc.1030.0052 2004
[14]

In: Bouman, P.C., Kontogiannis, S.C

Reiter, K., Schmidt, M., Stiglmayr, M.: The Line-Based Dial-a-Ride Problem. In: Bouman, P.C., Kontogiannis, S.C. (eds.) 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). pp. 14:1 – 14:20. Open Access Series in Informatics (OASIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024).https:/...

work page 2024
[15]

Networks22(3), 263–282 (1992).https://doi.org/10.1002/net

Tsitsiklis, J.N.: Special cases of traveling salesman and repairman problems with time windows. Networks22(3), 263–282 (1992).https://doi.org/10.1002/net. 3230220305

work page doi:10.1002/net 1992
[16]

Transportation Research Part C: Emerging Technologies137, 103573 (Apr 2022).https://doi

Vansteenwegen, P., Melis, L., Aktaş, D., Montenegro, B.D.G., Sartori Vieira, F., Sörensen, K.: A survey on demand-responsive public bus systems. Transportation Research Part C: Emerging Technologies137, 103573 (Apr 2022).https://doi. org/10.1016/j.trc.2022.103573

work page doi:10.1016/j.trc.2022.103573 2022
[17]

Networks57(2), 128–134 (2011).https://doi.org/10.1002/net.20393 Appendix Completion of Proofs for thePolynomially Solvable Cases Lemma 1 (⋆)

Yu, W., Liu, Z.: Single-vehicle scheduling problems with release and service times on a line. Networks57(2), 128–134 (2011).https://doi.org/10.1002/net.20393 Appendix Completion of Proofs for thePolynomially Solvable Cases Lemma 1 (⋆). Given a route, we can check in polynomial time whether it is feasible and, if so, complement it to a feasible tour. If th...

work page doi:10.1002/net.20393 2011
[18]

For each subsequent tourrT i , we proceed analogously, retaining for each waypoint except the first the time difference to the preceding waypoint

= 0 and, for each subsequent waypoint¯w1 j, we sett( ¯w1 j ) = t( ¯w1 j−1) + t(w1 j ) − t(w1 j−1), thus retaining the time difference to the preceding waypoint. For each subsequent tourrT i , we proceed analogously, retaining for each waypoint except the first the time difference to the preceding waypoint. For the first waypoint¯wi 1, we set t( ¯wi

work page
[19]

We haveγ = th( ¯wi−1 m(i−1)),h( ¯wi

= t( ¯wi−1 m(i−1)) + γ, where γ is the time constraint imposed by the time distance, as well as the service and turn time. We haveγ = th( ¯wi−1 m(i−1)),h( ¯wi

work page
[20]

If the toursri−1 and ri have different directions one turn is needed

+ ts + δ · tturn, with δ being the number of turns necessary between the two waypoints. If the toursri−1 and ri have different directions one turn is needed. Otherwise, both tours have the same direction. If the stop h( ¯wi−1 m(i−1)) is after h( ¯wi

work page
[21]

Otherwise, no turn is needed

in the direction of the tours, two turns are needed, as the vehicle has to drive back. Otherwise, no turn is needed. After applying this procedure to all tours, the time constraintsγ, imposed by the distances as well as the service and turn times, are fulfilled by construction. Further, the service promise is still fulfilled, as ride times did not change ...

work page
[22]

without time windows and without service promise

work page
[23]

without time windows, without shortcuts, and without service times

work page
[24]

In all cases, a subroute is feasible if and only if we do not violate the capacity:

without time windows and with a capacity of1 Proof. In all cases, a subroute is feasible if and only if we do not violate the capacity:

work page
[25]

As there are no time windows and no service promise, according to Lemma 1, the feasibility of a subroute depends only on the capacity constraints

work page
[26]

Thus, each passenger always arrives after their direct time dis- tance at their destination, regardless of other passengers transported by the vehicle

Since there are no service times as well as no shortcuts, picking-up and dropping-off a passenger does not cause a delay for the passengers already in the vehicle. Thus, each passenger always arrives after their direct time dis- tance at their destination, regardless of other passengers transported by the vehicle. Thus, the service promise is always kept ...

work page
[27]

Thus, the service promise is always kept and this case is equivalent to there being no service promise

Since the capacity of the vehicles is1, each passenger has to be transported individually, and is therefore driven directly to their destination. Thus, the service promise is always kept and this case is equivalent to there being no service promise. In order to obtain a minimum number of subroutes, we apply Lemma 4 to obtain in polynomial time the minimum...

work page
[28]

without time windows, shortcuts, and turn times, and

work page
[29]

without time windows, service times, and turn times. Proof. We show this for the first case by reducing3-Partitionto theMinTurn problem.Let (S, m, T)beaninstanceof 3-Partition.Weconstructa MinTurn instance as in the proof of Theorem 3 fork = 1. We then change the number of vehicles in this instance tom. As we have shown earlier,S has a3-partition if and o...

work page

[1] [1]

Transportation Research Part C: Emerging Technologies19(5), 741–750 (2011).https://doi.org/10.1016/j.trc.2009.12.006

Archetti, C., Feillet, D., Gendreau, M., Grazia Speranza, M.: Complexity of the VRP and SDVRP. Transportation Research Part C: Emerging Technologies19(5), 741–750 (2011).https://doi.org/10.1016/j.trc.2009.12.006

work page doi:10.1016/j.trc.2009.12.006 2011

[2] [2]

ACM Trans

Bjelde, A., Hackfeld, J., Disser, Y., Hansknecht, C., Lipmann, M., Meißner, J., Schlöter, M., Schewior, K., Stougie, L.: Tight bounds for online TSP on the line. ACM Trans. Algorithms17(1), 3:1–3:58 (2021).https://doi.org/10.1145/ 3422362

work page 2021

[3] [3]

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979).https://doi.org/10.5555/574848

work page doi:10.5555/574848 1979

[4] [4]

Gaul, D., Klamroth, K., Stiglmayr, M.: Event-based MILP models for ridepooling applications. Eur. J. Oper. Res.301(3), 1048–1063 (2022).https://doi.org/10. 1016/J.EJOR.2021.11.053

work page 2022

[5] [5]

Information Pro- cessing Letters 86(2), 87–91 (2003).https://doi.org/10.1016/S0020-0190(02) 00474-X

Gaur, D.R., Gupta, A., Krishnamurti, R.: A 53-approximation algorithm for scheduling vehicles on a path with release and handling times. Information Pro- cessing Letters 86(2), 87–91 (2003).https://doi.org/10.1016/S0020-0190(02) 00474-X

work page doi:10.1016/s0020-0190(02 2003

[6] [6]

Discrete Applied Math- ematics 81(1), 41–57 (Jan 1998)

Guan, D.J.: Routing a vehicle of capacity greater than one. Discrete Applied Math- ematics 81(1), 41–57 (Jan 1998). https://doi.org/10.1016/S0166-218X(97) 00074-7

work page doi:10.1016/s0166-218x(97 1998

[7] [7]

In: Chen, B

Haugland, D., Ho, S.C.: Feasibility Testing for Dial-a-Ride Problems. In: Chen, B. (ed.) Algorithmic Aspects in Information and Management. pp. 170–179. Springer, Berlin, Heidelberg (2010).https://doi.org/10.1007/978-3-642-14355-7_18

work page doi:10.1007/978-3-642-14355-7_18 2010

[8] [8]

Transporta- tion Research Part B: Methodological111, 395–421 (2018).https://doi.org/10

Ho, S.C., Szeto, W., Kuo, Y.H., Leung, J.M., Petering, M., Tou, T.W.: A survey of dial-a-ride problems: Literature review and recent developments. Transporta- tion Research Part B: Methodological111, 395–421 (2018).https://doi.org/10. 1016/j.trb.2018.02.001

work page 2018

[9] [9]

Discrete Mathematics306(19), 2529–2571 (2006)

Hougardy, S.: Classes of perfect graphs. Discrete Mathematics306(19), 2529–2571 (2006). https://doi.org/10.1016/j.disc.2006.05.021, creation and Recre- ation: A Tribute to the Memory of Claude Berge

work page doi:10.1016/j.disc.2006.05.021 2006

[10] [10]

Hua, Q., Wang, Y., Yu, D., Lau, F.C.M.: Dynamic programming based algorithms for set multicover and multiset multicover problems. Theor. Comput. Sci.411(26- 28), 2467–2474 (2010).https://doi.org/10.1016/J.TCS.2010.02.016

work page doi:10.1016/j.tcs.2010.02.016 2010

[11] [11]

In: auf der Heide, F.M

Karuno, Y., Nagamochi, H.: A 2-approximation algorithm for the multi-vehicle scheduling problem on a path with release and handling times. In: auf der Heide, F.M. (ed.) Algorithms — ESA 2001. pp. 218–229. Springer Berlin Heidelberg, Berlin, Heidelberg (2001).https://doi.org/10.1016/S0166-218X(02)00596-6

work page doi:10.1016/s0166-218x(02)00596-6 2001

[12] [12]

Networks 39(4), 203–209 (2002)

Karuno, Y., Nagamochi, H., Ibaraki, T.: Better approximation ratios for the single- vehicle scheduling problems on line-shaped networks. Networks 39(4), 203–209 (2002). https://doi.org/10.1002/net.10028

work page doi:10.1002/net.10028 2002

[13] [13]

INFORMS J

de Paepe, W., Lenstra, J.K., Sgall, J., Sitters, R.A., Stougie, L.: Computer-aided complexity classification of dial-a-ride problems. INFORMS J. Comput. 16(2), 120–132 (2004).https://doi.org/10.1287/IJOC.1030.0052

work page doi:10.1287/ijoc.1030.0052 2004

[14] [14]

In: Bouman, P.C., Kontogiannis, S.C

Reiter, K., Schmidt, M., Stiglmayr, M.: The Line-Based Dial-a-Ride Problem. In: Bouman, P.C., Kontogiannis, S.C. (eds.) 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). pp. 14:1 – 14:20. Open Access Series in Informatics (OASIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024).https:/...

work page 2024

[15] [15]

Networks22(3), 263–282 (1992).https://doi.org/10.1002/net

Tsitsiklis, J.N.: Special cases of traveling salesman and repairman problems with time windows. Networks22(3), 263–282 (1992).https://doi.org/10.1002/net. 3230220305

work page doi:10.1002/net 1992

[16] [16]

Transportation Research Part C: Emerging Technologies137, 103573 (Apr 2022).https://doi

Vansteenwegen, P., Melis, L., Aktaş, D., Montenegro, B.D.G., Sartori Vieira, F., Sörensen, K.: A survey on demand-responsive public bus systems. Transportation Research Part C: Emerging Technologies137, 103573 (Apr 2022).https://doi. org/10.1016/j.trc.2022.103573

work page doi:10.1016/j.trc.2022.103573 2022

[17] [17]

Networks57(2), 128–134 (2011).https://doi.org/10.1002/net.20393 Appendix Completion of Proofs for thePolynomially Solvable Cases Lemma 1 (⋆)

Yu, W., Liu, Z.: Single-vehicle scheduling problems with release and service times on a line. Networks57(2), 128–134 (2011).https://doi.org/10.1002/net.20393 Appendix Completion of Proofs for thePolynomially Solvable Cases Lemma 1 (⋆). Given a route, we can check in polynomial time whether it is feasible and, if so, complement it to a feasible tour. If th...

work page doi:10.1002/net.20393 2011

[18] [18]

For each subsequent tourrT i , we proceed analogously, retaining for each waypoint except the first the time difference to the preceding waypoint

= 0 and, for each subsequent waypoint¯w1 j, we sett( ¯w1 j ) = t( ¯w1 j−1) + t(w1 j ) − t(w1 j−1), thus retaining the time difference to the preceding waypoint. For each subsequent tourrT i , we proceed analogously, retaining for each waypoint except the first the time difference to the preceding waypoint. For the first waypoint¯wi 1, we set t( ¯wi

work page

[19] [19]

We haveγ = th( ¯wi−1 m(i−1)),h( ¯wi

= t( ¯wi−1 m(i−1)) + γ, where γ is the time constraint imposed by the time distance, as well as the service and turn time. We haveγ = th( ¯wi−1 m(i−1)),h( ¯wi

work page

[20] [20]

If the toursri−1 and ri have different directions one turn is needed

+ ts + δ · tturn, with δ being the number of turns necessary between the two waypoints. If the toursri−1 and ri have different directions one turn is needed. Otherwise, both tours have the same direction. If the stop h( ¯wi−1 m(i−1)) is after h( ¯wi

work page

[21] [21]

Otherwise, no turn is needed

in the direction of the tours, two turns are needed, as the vehicle has to drive back. Otherwise, no turn is needed. After applying this procedure to all tours, the time constraintsγ, imposed by the distances as well as the service and turn times, are fulfilled by construction. Further, the service promise is still fulfilled, as ride times did not change ...

work page

[22] [22]

without time windows and without service promise

work page

[23] [23]

without time windows, without shortcuts, and without service times

work page

[24] [24]

In all cases, a subroute is feasible if and only if we do not violate the capacity:

without time windows and with a capacity of1 Proof. In all cases, a subroute is feasible if and only if we do not violate the capacity:

work page

[25] [25]

As there are no time windows and no service promise, according to Lemma 1, the feasibility of a subroute depends only on the capacity constraints

work page

[26] [26]

Thus, each passenger always arrives after their direct time dis- tance at their destination, regardless of other passengers transported by the vehicle

Since there are no service times as well as no shortcuts, picking-up and dropping-off a passenger does not cause a delay for the passengers already in the vehicle. Thus, each passenger always arrives after their direct time dis- tance at their destination, regardless of other passengers transported by the vehicle. Thus, the service promise is always kept ...

work page

[27] [27]

Thus, the service promise is always kept and this case is equivalent to there being no service promise

Since the capacity of the vehicles is1, each passenger has to be transported individually, and is therefore driven directly to their destination. Thus, the service promise is always kept and this case is equivalent to there being no service promise. In order to obtain a minimum number of subroutes, we apply Lemma 4 to obtain in polynomial time the minimum...

work page

[28] [28]

without time windows, shortcuts, and turn times, and

work page

[29] [29]

without time windows, service times, and turn times. Proof. We show this for the first case by reducing3-Partitionto theMinTurn problem.Let (S, m, T)beaninstanceof 3-Partition.Weconstructa MinTurn instance as in the proof of Theorem 3 fork = 1. We then change the number of vehicles in this instance tom. As we have shown earlier,S has a3-partition if and o...

work page