Soft Requested-Time Targeting and Ride-Time Slack Collapse

[drogers0]

Hi @jcoupey,

I have been a long time user of VROOM and have implemented a VROOM-native three-phase solve strategy to address some of the rough edges that come with a pure constraint solver. In particular, for passenger-style PDPTW problems, we often need to express soft requested service times and reduce unnecessary ride-time slack without changing stop order.

Today, time windows are strictly hard constraints and waiting time is not part of the objective, which can produce feasible but operationally undesirable results (e.g., necessarily schedule for edge of time window or have early pickups followed by onboard dwell). The approach below works within existing VROOM semantics, but requires non-obvious manipulation of time windows and PLAN mode.

I have a wrapper that does something similar in my codebase, but would like to migrate it into the solver itself to increase performance, simplify my implementation, and open up additional functionality to Vroom users.

---

Phase 0

Run a VRP solve.

Phase 1 – Requested-Time Coercion

Goal: Bias solution service toward a requested pickup or dropoff time without breaking original feasibility.

Steps

3. For the priority stop (pickup or dropoff):

   • Preserve original time window as hard bounds:

     service_after  = original_lower_bound
     service_before = original_upper_bound
     

   • Replace time_windows with a tight window around the requested time:

     time_windows = [requested_time ± ε]
     

4. Re-solve in plan mode

Effect

• Solver attempts to hit requested times (misses are balanced across trips and reported as "violations")
• Original window remains enforced via hard bounds.
• Stop order is unchanged.

---

Phase 2 – Ride-Time Slack Collapse

Goal: Remove unnecessary onboard dwell while preserving sequence and requested-time alignment.

Steps

1. Extract scheduled times from Phase 1.

2. For each priority stop:

   • Freeze the scheduled time:

     service_at = scheduled_time_from_phase_1
     

3. For each non-priority stop:

   • Tighten time_windows around the priority stop service_at time:

     time_windows = [priority_stop_service_at ± ε]
     

     travel times could be incorporated here to avoid biasing balancing toward longer trips

   • Keep existing:

     service_after
     service_before
     

4. Re-solve in plan mode

Effect

• Solver collapses slack where possible (misses are balanced across trips and reported as "violations")
• Original window remains enforced via hard bounds.
• Stop order is unchanged.
• Requested-time alignment is preserved.

---

Proposal

Add native support for soft requested times and slack collapse through api update and internal implementation of logic described above.

example api update:

job/shipment_step

Key	Description
target_time	a timestamp describing prefered servicing time (in shipments, can only be used on pickup or dropoff, not both)
anchor	id of the shipment_step or job that anchors compaction

---

I would be happy to contribute documentation or discuss implementation approaches.
If we are aligned, I could start work on putting a PR forward.

Thank you!

[jcoupey]

Thanks for describing this workflow in detail!

I get it that for your use-case the default presentation of the solution is not ideal and my understanding is that the resulting plan you get after phase 2 has better properties in that regard (e.g. some steps are closer to an expected "target time"). In order to make sure I fully understand the big picture, I wonder if the final plan after your treatment is still a valid solution to the initial problem from phase 0?

[drogers0]

Yes, the final plan remains a valid solution to the original Phase-0 problem.
The original constraints are never relaxed or replaced; they are only augmented during the intermediate solves to bias the solver toward a preferred schedule.

The original time window bounds are retained throughout the workflow via:

service_after  = original_lower_bound
service_before = original_upper_bound

These remain the true hard constraints in every phase. The temporary time_windows modifications only act as a guidance mechanism in PLAN mode.

---

I went ahead and generated this all-in-one example showing phase 1 (requested time coercion) changing the total delta from requested time from 3.3k seconds to 300 seconds, and phase 2 Ride-Time Slack Collapse dropping the onboard dwell from 2.5k seconds to 521 seconds all while meeting original service constraints.

rideshare_dwell_phase0.json
rideshare_dwell_phase1.json
rideshare_dwell_phase2.json

[jcoupey]

Thanks for elaborating, it is especially useful to have a minimal example with an illustration.

The fact that you're generating a solution that is still valid (actually the same solution in terms of ordering, but different task times) confirms my first understanding that you're not interested in a different solution, but rather another presentation of the same solution.

Whenever we have margin to decide task times, the presentation of the solution we provide is just one option among many (often continuous) possibilities. The current default behavior is to:

1. pick the earliest start time for the last task (thus minimizing completion time);
2. go backward through the route to choose the latest possible matching start time for the first task (thus minimizing internal waiting time);
3. go through the route in order to decide actual start times, picking ASAP times.

This is clearly illustrated in the phase 0 setup above, and while this approach works well for typical delivery routes, what you're suggesting is in fact that this presentation is not ideal when moving people around.

Now what is not totally clear to me is how to leverage various other factors that could influence the presentation, because there are several metrics that may contribute (or conflict) in the presentation choice: closeness to a "requested" time, overall time spent on board for a customer, time spent waiting for passengers (or vehicles which is different).

[drogers0]

Thank you, yes the “alternate presentation” is the right framing.

I don't know if there is a single correct way to arbitrate between competing timing preferences. For my scenario, I would likely want a weighted relationship that biases toward closeness to the requested time, while still accounting for total time spent on board for a customer and largely ignoring makespan.

My wrapper and original plan treated these as hierarchical instead of weighted, but this would be ideal

More broadly, though, I think the right tradeoff will depend on the use case. That being said, the existing behavior already applies a specific hierarchy by first minimizing makespan and then “targeting” earliest service, which is itself an implicit schedule-selection policy suited to one class of problems, so any change that gives another option would be an improvement.

If I were to propose a fully configurable spec, it would likely be something like:

{
  "options": {
    "timing_objective": {
      "mode": "hierarchical",
      "objectives": ["target_time", "shipment_span", "makespan"]
    }
  }
}

{
  "options": {
    "timing_objective": {
      "mode": "weighted",
      "weights": {
        "target_time": 3,
        "shipment_span": 2,
        "makespan": 1
      }
    }
  }
}

and

{
  "job": {
      "target_time": 123
}

with earlyness as an implied schedule-selection bias / tie-breaker. This would make the default behavior reproducible with "objectives": ["makespan"]

I am not attached to exposing or implementing that full level of configurability immediately. A one-size-fits-most first step may be more appropriate: simply add target_time, and let its presence or a more simple options flag trigger a built-in arbitration policy along the lines described above. That would keep the API simple, preserve current behavior when target_time is absent, and still provide a useful native mechanism for cases where the default timing realization is not the desired one.

[jcoupey]

Coming up with a schedule that balances several objectives is already a hard optimization problem: the plan mode does solve a mixed integer linear program under the hood.

I think the right tradeoff will depend on the use case.

I'm not sure we want to bloat the solve API with this kind of complexity, especially as it's only about the schedule presentation (which may be confusing as we're never actually optimizing for makespan anyway).

There are probably a couple low-hanging fruits, e.g. scheduling pickup tasks "as late as possible" in step 3 of the process described above to compress passenger dwell, or including a notion of "target time" in plan mode (probably not that easy!).

[drogers0]

If we are okay with the behavior I think I can implement an MILP enhancement that:

• implements a target_time on jobs and shipment steps with timing presentations biased toward it
• preserves the existing makespan squeeze behavior (when it does not conflict with target time)
• always pushes pickup tasks as late as possible within feasibility (when it does not conflict with target time).
  • possibly some 2:1 balancing to handle conflicts here (2 minutes of shipment span = 1 minute of target miss)

I've done some scanning and I have an initial plan if you wanted to give me any pointers:

My understanding is that the MILP changes will have to go into src/algorithms/validation/choose_ETA.cpp. I propose changing choose_ETA.cpp to keep the current first-pass solve and pin only the optimal Sigma_Y violation total, then run a second pass where target-time deviation and shipment span are optimized as a weighted sum.

For solve mode I propose making src/utils/helpers.cpp::format_solution route the solved paths straight into choose_ETA.cpp for final timing assignment, instead of using format_route_simple / format_route to compute step times. This will ensure consistency between the solve and plan presentations and cut down on duplicated logic. I know there's performance considerations here but I think parameterizing or splitting the glp out of choose_ETA would handle it more cleanly.

[jcoupey]

If you're willing to dig into the MILP itself, you could probably get it to adjust the scheduling presentation to suit your needs. This means you could get your expected result in just one go through choose_ETA (either with a single dedicated plan request or by replacing format_solution as you mention). Note that this would probably not be trivial since there are already some big-M tricks for existing hierarchical objectives.

Now the thing is that if you do that you'll be hard-coding some assumptions (typically "2 minutes of shipment span = 1 minute of target miss" and any other ponderation decision that occur in the model). Those assumptions will be the right ones for your use-case, just like the current implementation is the right one for some use-cases, but I don't really see how you can make this generic.

I propose making src/utils/helpers.cpp::format_solution route the solved paths straight into choose_ETA.cpp for final timing assignment, instead of using format_route_simple / format_route to compute step times

I totally get the point about consistency, especially as it has been a deep concern when implementing plan mode in the first place and have indeed required to duplicate some of the logic. On the other hand, solving a MILP for each route just for the sake of selecting arrival times while we currently do this in linear time is a huge performance red flag.

[drogers0]

Thanks for the pointers, I've been prototyping this in the MILP and I think I have an approach.

Looking at the existing choose_ETA structure, the big-M tricks are all in pass 1 (violations >> makespan). Pass 2 pins the optimal violations and makespan, then minimizes earliness. My changes would only touch that second pass. I'd keep the violation pin but release the makespan pin, letting it compete as a weighted term alongside target deviation and shipment span in the objective.

On genericity: I'm thinking of implementing the second pass as a single weighted objective over three terms: makespan, target-time deviation, and shipment span. The weights would be compile-time constants for now, which gives sensible defaults without any API change beyond target_time on jobs/shipment steps. But structurally it's just coefficients in the LP objective function, so if there is a desire to expose them (e.g. vehicles[].makespan_weight, jobs[].target_weight, shipments[].span_weight or more global options) it's a trivial addition.

On performance: I'm not proposing to route all solve-mode results through the MILP approach. The plan is:
Plan mode: uses choose_ETA as it does today, with the weighted objective in pass 2
Solve mode: only routes with target_time jobs go through choose_ETA for timing assignment and when they do they bypass the first pass (no violation minimization needed since routes are already feasible). Routes without target_time keep the existing linear-time format_route/format_route_simple path so no overhead for existing behavior. I think this effort could be split though and only worry about plan mode for now.

If you are okay with this approach, I could try to PR something next week. Functional changes would be

• adding a target_time api param to jobs/shipment_steps
• modifying the chooseETA phase 2 MILP to be a weighted objective over makespan, target-time deviation, and shipment span.

From there we could talk about solve mode and api surface follow ups

[drogers0]

@jcoupey, let me know if this change would be desirable. Since it changes the api surface I don't want to do anything without you giving the go ahead.

Functional changes would be

• adding a target_time api param to jobs/shipment_steps
• modifying the chooseETA phase 2 MILP to be a weighted objective over makespan, target-time deviation, and shipment span.

From there we could talk about solve mode and api surface follow ups

[jcoupey]

Sorry @drogers0 for the delay here. On one hand, I get it that providing better control on the solution layout is interesting in some situations, on the other hand I fear that introducing a target_time parameter for that purpose could be misleading. In fact that would be the only key in the whole solve API that does not introduce a hard constraint, but some kind of (presentation) preference.

This could be hard to figure out and explain: think of a situation where a solution matching all target_time for all tasks exists. Just by reading the API, I guess most new users would expect us to provide exactly that solution. But then if a cheaper solution exists that is much worse in terms of target_time deviation, that is the one we'll provide and I can see how frustrating that could be, especially for very tiny cost differences.

I guess my concern here would be the same for introducing any "soft" constraint or "preference" side-cost on the solving side: the elephant in the room is how to treat that additional cost.

[drogers0]

I was proposing something closer to the existing plan-mode behavior: service_* constraints are not part of normal solve-mode route selection, and time_windows already become “soft” in plan mode in the sense that choose_ETA minimizes/reports violations for a fixed route. So there is already precedent for plan-only timing semantics.

I understand the confusion, because at points I was thinking and talking about solve mode as well, but in the last message I suggested deferring any solve mode changes until we could align on what that would mean and moving forward with:

• adding a target_time api param to jobs/shipment_steps
• modifying the chooseETA phase 2 MILP to be a weighted objective over makespan, target-time deviation, and shipment span.

Since the chooseETA is only called from the plan mode path and unused params are ignored the result of this would be similar to existing plan only params.