Breaks steps have meaningless location_index values in output

[fbaierl]

Hello,

we noticed a strange behavior using VROOM v1.13-rc1. It seems that the break (sometimes?) does not get a location attached in the result json. Instead, a "location_index": 0 is added to the break even though we did not provide a custom location matrice or something similar.

For now we fix this issue by just assuming the breaks location to be at the step happening before or afterwards depending on the distance.

Input

{
    "vehicles": [
        {
            "id": 0,
            "description": "715c9061-e484-43bd-a631-f2d1da30e728",
            "start": [
                12.304373066846503,
                51.62270653765847
            ],
            "end": [
                12.304373066846503,
                51.62270653765847
            ],
            "capacity": [
                7,
                1
            ],
            "skills": [
                2,
                3,
                11,
                5
            ],
            "time_window": [
                1674601200,
                1674687540
            ],
            "breaks": [
                {
                    "id": 0,
                    "time_windows": [
                        [
                            1674633570,
                            1674647970
                        ]
                    ],
                    "service": 7200,
                    "max_load": [
                        0,
                        0
                    ]
                }
            ]
        }
    ],
    "jobs": [],
    "shipments": [
        {
            "amount": [
                1,
                0
            ],
            "skills": [
                2,
                5
            ],
            "priority": 0,
            "pickup": {
                "id": 0,
                "setup": 60,
                "service": 0,
                "location": [
                    12.219437,
                    51.715622
                ],
                "time_windows": [
                    [
                        1674610440,
                        1674612240
                    ]
                ],
                "description": "pickup|9bc34259-e8d2-479d-a9f4-4722a4c0fc0d"
            },
            "delivery": {
                "id": 1,
                "setup": 60,
                "service": 0,
                "location": [
                    12.175563,
                    51.694164
                ],
                "time_windows": [
                    [
                        1674612240,
                        1674613560
                    ]
                ],
                "description": "delivery|9bc34259-e8d2-479d-a9f4-4722a4c0fc0d"
            }
        }
    ]
}

Output

{
    "code": 0,
    "summary": {
        "cost": 2759,
        "routes": 1,
        "unassigned": 0,
        "delivery": [
            1,
            0
        ],
        "amount": [
            1,
            0
        ],
        "pickup": [
            1,
            0
        ],
        "setup": 120,
        "service": 7200,
        "duration": 2759,
        "waiting_time": 19445,
        "priority": 0,
        "distance": 43395,
        "violations": [],
        "computing_times": {
            "loading": 14,
            "solving": 0,
            "routing": 4
        }
    },
    "unassigned": [],
    "routes": [
        {
            "vehicle": 0,
            "cost": 2759,
            "description": "715c9061-e484-43bd-a631-f2d1da30e728",
            "delivery": [
                1,
                0
            ],
            "amount": [
                1,
                0
            ],
            "pickup": [
                1,
                0
            ],
            "setup": 120,
            "service": 7200,
            "duration": 2759,
            "waiting_time": 19445,
            "priority": 0,
            "distance": 43395,
            "steps": [
                {
                    "type": "start",
                    "location": [
                        12.304373066846503,
                        51.62270653765847
                    ],
                    "setup": 0,
                    "service": 0,
                    "waiting_time": 0,
                    "load": [
                        0,
                        0
                    ],
                    "arrival": 1674611246,
                    "duration": 0,
                    "violations": [],
                    "distance": 0
                },
                {
                    "type": "pickup",
                    "description": "pickup|9bc34259-e8d2-479d-a9f4-4722a4c0fc0d",
                    "location": [
                        12.219437,
                        51.715622
                    ],
                    "id": 0,
                    "setup": 60,
                    "service": 0,
                    "waiting_time": 0,
                    "job": 0,
                    "load": [
                        1,
                        0
                    ],
                    "arrival": 1674612240,
                    "duration": 994,
                    "violations": [],
                    "distance": 13552
                },
                {
                    "type": "delivery",
                    "description": "delivery|9bc34259-e8d2-479d-a9f4-4722a4c0fc0d",
                    "location": [
                        12.175563,
                        51.694164
                    ],
                    "id": 1,
                    "setup": 60,
                    "service": 0,
                    "waiting_time": 0,
                    "job": 1,
                    "load": [
                        0,
                        0
                    ],
                    "arrival": 1674612822,
                    "duration": 1516,
                    "violations": [],
                    "distance": 20653
                },
                {
                    "type": "break",
                    "location_index": 0,
                    "id": 0,
                    "setup": 0,
                    "service": 7200,
                    "waiting_time": 19445,
                    "load": [
                        0,
                        0
                    ],
                    "arrival": 1674614125,
                    "duration": 2759,
                    "violations": [],
                    "distance": 43395
                },
                {
                    "type": "end",
                    "location": [
                        12.304373066846503,
                        51.62270653765847
                    ],
                    "setup": 0,
                    "service": 0,
                    "waiting_time": 0,
                    "load": [
                        0,
                        0
                    ],
                    "arrival": 1674640770,
                    "duration": 2759,
                    "violations": [],
                    "distance": 43395
                }
            ],
            "violations": [],
            "geometry": "_razH{dbjAk@_GCS_A\\s@XMDSPMDKByAXSBe@Bk@HWHFl@LpAZtC@LDh@QFgBp@kDnAWHy@ZKDaEzA_@Li@T{EdBkFnBcBl@uGbC_AZeAb@_@N_@N]NIBUJ}@\\yNpFqG`Cu@Ne@NuAb@_@LaA^]PIHKFkE|C_Av@qBzAo@b@aEtCwClBiAx@w@~@[`@W`@m@xA}@jBYj@KTUl@Ud@Uf@_@p@_@r@y@|@oErEiFrFUTwU~V]b@y@`Bm@pAo@rAuAjCi@dA]v@OXeBjDg@jA{B|EcDhHEJWl@ABQ~@CJi@rEQtACRq@]{Au@i@W}@a@]Q[M[IGCe@MkAWaAKaE]c@GqD[g@GyAK_@?_ABgANOBeBb@iCt@_Bl@_@NIB]P_@Tq@f@iAr@KHa@VYHc@JuBJSCgCW}B[i@GSKcA_@UOYSg@g@Y]aAmAIIMKOIOGMEEAICOCaBUuAQ_@E]Aq@Bg@JUFYL_@Rm@^_CpASJo@T[Fa@BE@]BuBRyAJM@mAHaAFqAE_@C}AG_AE{@Eq@Aq@?iAJ]DMBm@J{@PsBb@k@FSBcANu@Ba@B{@DkAHq@DSBsARcATYHgAVo@NcCj@UF]H{Bh@IB_B\\a@HmDt@eDz@qBb@uBf@]LYJA@SHMBKJCBABCBUh@Yt@I\\G\\EZGn@Ap@WvOCl@GxBEv@Iv@Kj@IXIVOZMNOLMFKD_@Jg@Ne@NYNk@\\{BjAc@R}FlCmCnAeAd@c@Ra@Pg@X]Tq@d@]ZGDOLGDoB|As@h@u@n@kStPoTrQkB~AaEdDqAdAcEjDmMnKyM|KsDzCO~AiCrZgAdNoFjo@iB|Te@dFAHw@pGMd@Ob@Uf@e@r@KNeBnCN\\J^@d@BnBF|CHtBIFELCNYrI?~@FdAZfD[gDGeA?_AXsIBODMHGIuBG}CCoBAe@K_@O]MXO\\M^W~@YlAw@pEYvAa@`BGP]nAYrAg@vCQ~@Oz@YjBUzAOhAQbBStBS`COfCGnBGlBATQfF?BEfBA|@?vA?bADfBDlAHrAJxALtAN|APhCFtAFbB?tBUfMaDncBWxNIdDGlDAt@A`@C\\VLVHRDp@Fh@@fEOlAInAKbBU|AS|@Kn@GXEpAM~DQnAEvAEl@?b@FjBb@`ARb@Bn@Ex@MnImBj@Mh@Sh@_@ZSVK`@CN@P?VBPA\\A`@IvBc@dH}A~FmAzG{AbRyDfAfQLtBBjA?zAGbP?lC@nADbADx@JjATrAPz@XbA\\z@\\t@d@v@p@dAn@bAp@jAf@bA^lAf@|BVhBTvCHVHHN@pCq@t@Sp@QfA[vBo@LDE_BAwD?gA?g@?f@?fA@vDD~AMEwBn@gAZq@Pu@RqCp@OAIIIWUwCWiBg@}B_@mAg@cAq@kAo@cAq@eAe@w@]u@]{@YcAQ{@UsAKkAEy@EcAAoA?mCFcP?{ACkAMuBgAgQcRxD{GzA_GlAeH|AwBb@a@H]@Q@WC?aB@yF?iBPq~@Hil@?oG?wHBqL_@?}AAs@AWCSCUMYUU_@Ww@Gu@Bm@Bm@Je@Re@\\_@TOLGZUl@FrBTbGn@~|@vJt@J\\BxANtp@nHt@Ht}@zJlv@nIx@JjKjAn~@|JbBP`QtB`I`AxNxAdALlL`BrKlBnAT|H`BdKbC|Cx@hEfAtEpAdElArHzBfBh@Jh@RVVn@Jl@@t@Gr@I^O\\[\\WJS@YEu@Se@OsAa@WCDyG?[?iB?qB?aBAiAEiBAS?GEmBIuCK_D[cGMcBk@{HoF{j@m@qGMmAe@qFKcAEc@OyAk@mGi@yEo@{GCWyN}zAo@eFm@_Ec@oCe@oCWyAg@kCIa@[}AI[ScAc@yBg@eCYuAcA{E_@oBWkBQeAKeAU{CeAca@CwC@uBLqGn@_SXuIPeDPuCZiDZyC`@}Cf@yCr@kDv@cDz@aD`AwC`CiGfCiGdS_f@hC_F`BqCh@w@^i@l@}@h@s@`AiAnAsApAmAbDoChCcBhCyAXQ`DqAdDmAdEwA~DeAnKoCl@Ij@Dn@Jh@Nd@XlC~A~@h@PJ^RLHFo@H{@F_@J{@He@dAwGh@eD^uBZiBBKBUF]L}@X_CH{@F{@DsAAe@CmAKqBSuBOgBKw@g@eFGq@S_CK_AY}CAOWuCw@eIWaCCQs@iHO}AKgAWcCa@_EGm@e@sEEi@AM[uCMqAGm@VIj@Id@CRCxAYJCLET?bC{@j@~F"
        }
    ]
}

[jcoupey]

Thanks for reporting. Actually breaks are not supposed to have a location in output, see for example https://github.com/VROOM-Project/vroom/blob/master/docs/example_1_sol.json. It has always been this way, so the problem here is that we report a meaningless location_index (the 0 value is a default value since no location has ever been set for the break step).

The problem is that we don't discriminate between steps types when serializing to json. No-one spotted this since it has been introduced back in #627.

[jcoupey]

Actually we should probably make the Step::location member optional here, as it would be easy to check that upon serialization. Also it would provide a cleaner interface for users of the C++ interface.

[fbaierl]

Thanks for the fast reply (and happy new year). Originally, I assumed that the break always happens at the location of the previous step. This was true before I think - now it always seems to happen at the location of the next step for some reason.

What I find a bit strange in my example is that the the vehicle is driving to the end-location after the last delivery and before the break happens at that (end-) location, there is an additional waiting time before the break begins. While technically not wrong, this seems odd. Is there a reason for that?

Also, isn't it a bit tedious to have to check the 'distance' value of the break to determine its location?

[jcoupey]

Breaks can basically happen anywhere/anytime between the adjacent tasks. Even if they can stick to the previous or next task, we want to have a lot of flexibility here. The rationale is that in a T1 -> Break -> T2 setup, we have the ability to split the T1 -> T2 travel time across the break. Typically if the break and T2 have later TW, you don't want to wait before taking the break. In that case we'll do as much of the travel we can, start the break ASAP, then do the rest after the break.

The intermediate distance value for the break has no real significance since there is no actual location. It is just computed based on travel time split for consistency here.

[fbaierl]

For me it seems the distance value is always either the same as for the previous step or the following step. I have never seen a break with a distance in between.

Is there another way of recognizing at what part of the travel the break is taken? For our algorithm I think I would need to iterate over the breaks and manually shift them back or forth so that they are always exactly after/before another step.

[jcoupey]

For me it seems the distance value is always either the same as for the previous step or the following step.

It means you only encountered situations with the break right after or right before a job. Having the travel time split across a break only happens under special TW circumstances where fitting the break would otherwise be impossible.

Is there another way of recognizing at what part of the travel the break is taken?

The steps[].arrival keys (combined with duration values) will provide that information. If a break happens right after job j, then the break duration value is j.duration and its arrival will be j.arrival + j.waiting_time [+ j.setup] + j.service.

the break happens at that (end-) location, there is an additional waiting time before the break begins. While technically not wrong, this seems odd. Is there a reason for that?

Breaks are mandatory so they'll show up in routes no matter what, even if everything can be done early and the vehicle reached its end location before the break available time. If you have a business logic where the break is only meaningful if the route is long enough, then you probably want to remove the "end break" from the route plan altogether in a post-processing step.

[fbaierl]

Alright, thank you very much. That explains a lot.

I have adapted our code to post-process the break accordingly (either attach it to previous or next step). Here is how I have done it (in case someone else has the same requirements):

   // handles the vroom behavior described here: https://github.com/VROOM-Project/vroom/issues/877
    // -> give break step a location
    // -> attach the break to the previous or next step
    private List<Step> postProcessBreakSteps(List<Step> steps) {
        final var ss = new ArrayList<>(steps);
        for (int i = 0; i < steps.size(); i++) {
            if (ss.get(i).isBreak() &&
                i > 0 && i < steps.size() - 1) { // actually not necessary, since start/end are always the first/last step! just to be extra-safe
                final var breakStep = ss.get(i);
                final var previousStep = ss.get(i - 1);
                final var nextStep = ss.get(i + 1);

                // decide, whether to attach the break to the previous or the next step by comparing the arrival difference
                final var midOfBreak = breakStep.getArrival() + (breakStep.getService() * 0.5);
                final var arrivalDifferenceToPrevious = Math.abs(previousStep.getArrival() - midOfBreak);
                final var arrivalDifferenceToNext = Math.abs(nextStep.getArrival() - midOfBreak);
                final var breakAfterPreviousStep = arrivalDifferenceToPrevious <= arrivalDifferenceToNext;
                // then calculate the updated break values
                final var breakLocation = breakAfterPreviousStep
                    ? previousStep.getLocation()
                    : nextStep.getLocation();
                final var breakArrival = breakAfterPreviousStep
                    ? previousStep.getArrival() + previousStep.getWaitingTime() + previousStep.getService() + previousStep.getSetup() // right after previous step has finished
                    : nextStep.getArrival() - breakStep.getService();                                                                 // right before the next step
                final var breakWaitingTime = breakAfterPreviousStep
                    ? 0                             // right after previous step -> no waiting time; add the waiting time to the next step
                    : breakStep.getWaitingTime();   // no need to update the waiting time if we just shift the break to a later time
                final var nextStepWaitingTime = breakAfterPreviousStep
                    ? breakWaitingTime + breakStep.getWaitingTime()
                    : nextStep.getWaitingTime();
                final var nextStepArrival = breakAfterPreviousStep
                    ? nextStep.getArrival() - breakStep.getWaitingTime()
                    : nextStep.getArrival();
                final var breakDistance = breakAfterPreviousStep
                    ? previousStep.getDistance()
                    : nextStep.getDistance();
                final var breakDuration = breakAfterPreviousStep
                    ? previousStep.getDuration()
                    : nextStep.getDuration();

                // update break
                ss.set(i, new Step(
                    breakStep.getType(),
                    breakArrival,
                    breakDuration,
                    breakStep.getSetup(),
                    breakStep.getLoad(),
                    breakStep.getService(),
                    breakWaitingTime,
                    breakStep.getViolations(),
                    breakStep.getDescription(),
                    breakStep.getId(),
                    breakDistance,
                    breakLocation
                ));

                // update next step
                ss.set(i + 1, new Step(
                    nextStep.getType(),
                    nextStepArrival,
                    nextStep.getDuration(),
                    nextStep.getSetup(),
                    nextStep.getLoad(),
                    nextStep.getService(),
                    nextStepWaitingTime,
                    nextStep.getViolations(),
                    nextStep.getDescription(),
                    nextStep.getId(),
                    nextStep.getDistance(),
                    nextStep.getLocation()
                ));
            }
        }
        return ss;
    }