Sequence of pickup-dropoff

[phat96]

What if I have sequence of pickup and dropoff with fixed order like (PU - PU - PU - DO - PU - DO) and would like to assign this whole sequence to 1 vehicle. Do this project support optimizing this scenario?

From the document, I see that [group] property of job could do something similar to my requirement (all tasks in groups would be assigned in 1 tour or drop them all) but look like It don't support to assign task with defined order and I didn't find example about this property.

[reinterpretcat]

Hi, have you checked relations [1] feature? It is designed to model vehicle-job relationship and supports strict sequence of jobs in the specific vehicle. For the job with multiple activities, you would need to specify the same job id multiple times (once for each activity).

[1] https://reinterpretcat.github.io/vrp/concepts/pragmatic/problem/relations.html

[phat96]

thanks you, exactly what I was looking for. Will test it soon

[phat96]

I just tested this feature. It could only solve part of my problem since Relations ask to clarify specific vehicle, while my requirement is letting Optimizer decide this itself.
Do you have any other ideas for this?

[reinterpretcat]

That's not directly supported. I think it is possible to implement, but will require some work.

Maybe one of possible workarounds is to use order property which will model the ordering of the jobs in any tour and group which will lock jobs to the one, not known upfront, vehicle. However, these features have impact on performance.

See docs here: https://reinterpretcat.github.io/vrp/concepts/pragmatic/problem/jobs.html

[phat96]

So, 'order' is applied for all tasks in the problem, no matter they belong in different jobs or not?
This would be the best option for now. The disadvantage is that order only prefer to handle tasks in defined order, not strictly follow it.

I think we still need to implement a feature that we don't have to define vehicleId in relations. That would make optimizer more flexible.

[phat96]

ah, another disadvantage is that if I have 4 sequences and I want them handled parallely by 4 vehicles, order would not be a good option, isn't it?

[reinterpretcat]

If order property is specified, then all jobs without order set are considered with the least possible order. Additionally, a tour_order objective function is taken into consideration with is_constrained=false. This means that by default the order is preferred, but not constrained. You can override objective manually with is_constrained=true to make it constrained, e.g.:

"objectives": [
    [
      {
        "type": "minimize-unassigned"
      }
    ],
    [
      {
        "type": "minimize-tours"
      }
    ],
    [
      {
        "type": "tour-order"
        "isConstrained": true
      }
    ],
    [
      {
        "type": "minimize-cost"
      }
    ]
  ]

ah, another disadvantage is that if I have 4 sequences and I want them handled parallely by 4 vehicles, order would not be a good option, isn't it?

Order doesn't provide directly the way to distribute jobs between different vehicles. Theoretically, you can use skills to lock specific jobs to specific vehicle types.

[phat96]

I have 3 sequences:

• ['945869', '945870']
• ['945871', '945873', '945874', '945872']
• ['944410', '944411']

Is this the correct way to constraint all tasks in sequence must be handled by 1 vehicle and correct order?

{
    "plan": {
        "jobs": [
            {
                "id": "945869",
                "group": "group_0",
                "pickups": [
                    {
                        "places": [
                            {
                                "location": {"lat": 1.3028787, "lng": 103.8343718},
                                "duration": 300,
                                "times": [
                                    [
                                        "2021-12-03T05:55:00.000Z",
                                        "2021-12-03T07:55:00.000Z",
                                    ]
                                ],
                            }
                        ],
                        "demand": [10, 5, 1],
                        "order": 1,
                    }
                ],
                "value": 5000.0,
            },
            {
                "id": "945870",
                "group": "group_0",
                "deliveries": [
                    {
                        "places": [
                            {
                                "location": {"lat": 1.2966426, "lng": 103.7763939},
                                "duration": 300,
                                "times": [
                                    [
                                        "2021-12-03T08:55:00.000Z",
                                        "2021-12-03T11:55:00.000Z",
                                    ]
                                ],
                            }
                        ],
                        "demand": [0, 0, 0],
                        "order": 2,
                    }
                ],
                "value": 5000.0,
            },
            {
                "id": "945871",
                "group": "group_1",
                "pickups": [
                    {
                        "places": [
                            {
                                "location": {"lat": 1.3094476, "lng": 103.882367},
                                "duration": 300,
                                "times": [
                                    [
                                        "2021-12-03T04:45:00.000Z",
                                        "2021-12-03T04:45:00.000Z",
                                    ]
                                ],
                            }
                        ],
                        "demand": [10, 0, 1],
                        "order": 1,
                    }
                ],
                "value": 5000.0,
            },
            {
                "id": "945873",
                "group": "group_1",
                "deliveries": [
                    {
                        "places": [
                            {
                                "location": {"lat": 1.363964, "lng": 103.832051},
                                "duration": 300,
                                "times": [
                                    [
                                        "2021-12-03T04:45:00.000Z",
                                        "2021-12-03T12:55:00.000Z",
                                    ]
                                ],
                            }
                        ],
                        "demand": [0, 0, 0],
                        "order": 2,
                    }
                ],
                "value": 5000.0,
            },
            {
                "id": "945874",
                "group": "group_1",
                "pickups": [
                    {
                        "places": [
                            {
                                "location": {"lat": 1.2828536, "lng": 103.8036075},
                                "duration": 300,
                                "times": [
                                    [
                                        "2021-12-03T04:45:00.000Z",
                                        "2021-12-03T12:55:00.000Z",
                                    ]
                                ],
                            }
                        ],
                        "demand": [10, 0, 1],
                        "order": 3,
                    }
                ],
                "value": 5000.0,
            },
            {
                "id": "945872",
                "group": "group_1",
                "deliveries": [
                    {
                        "places": [
                            {
                                "location": {"lat": 1.3223009, "lng": 103.9025671},
                                "duration": 300,
                                "times": [
                                    [
                                        "2021-12-03T08:55:00.000Z",
                                        "2021-12-03T12:55:00.000Z",
                                    ]
                                ],
                            }
                        ],
                        "demand": [0, 0, 0],
                        "order": 4,
                    }
                ],
                "value": 5000.0,
            },
            {
                "id": "944410",
                "group": "group_2",
                "pickups": [
                    {
                        "places": [
                            {
                                "location": {"lat": 1.2782636, "lng": 103.8481705},
                                "duration": 300,
                                "times": [
                                    [
                                        "2021-12-01T08:50:00.000Z",
                                        "2021-12-01T09:50:00.000Z",
                                    ]
                                ],
                            }
                        ],
                        "demand": [10, 0, 1],
                        "order": 1,
                    }
                ],
                "value": 5000.0,
            },
            {
                "id": "944411",
                "group": "group_2",
                "deliveries": [
                    {
                        "places": [
                            {
                                "location": {"lat": 1.3319582, "lng": 103.9645876},
                                "duration": 300,
                                "times": [
                                    [
                                        "2021-12-01T10:50:00.000Z",
                                        "2021-12-01T11:50:00.000Z",
                                    ]
                                ],
                            }
                        ],
                        "demand": [0, 0, 0],
                        "order": 2,
                    }
                ],
                "value": 5000.0,
            },
        ]
    },
    "fleet": {
        "profiles": [{"name": "car"}],
        "vehicles": [
            {
                "typeId": "2427",
                "vehicleIds": ["0-2427"],
                "profile": {"matrix": "car"},
                "costs": {"fixed": 35, "distance": 1, "time": 0},
                "shifts": [
                    {
                        "start": {
                            "earliest": "2020-12-03T05:05:32.683Z",
                            "location": {"lat": 37.785834, "lng": -122.406417},
                        }
                    }
                ],
                "capacity": [1, 1, 1],
            },
            {
                "typeId": "529",
                "vehicleIds": ["1-529"],
                "profile": {"matrix": "car"},
                "costs": {"fixed": 35, "distance": 1, "time": 0},
                "shifts": [
                    {
                        "start": {
                            "earliest": "2020-12-03T05:05:32.684Z",
                            "location": {"lat": 1.348877, "lng": 103.8745212},
                        }
                    }
                ],
                "capacity": [333, 333, 333],
            },
        ],
    },
    "objectives": [
        [{"type": "minimize-unassigned"}],
        [{"type": "minimize-tours"}],
        [{"type": "tour-order", "isConstrained": True}],
        [{"type": "maximize-value"}],
        [{"type": "minimize-cost"}],
    ],
}

Or should I add whole sequence to 1 job and set group name (group_1), set order for tasks like this?

{
    "id": "945871_945873_945874_945872_",
    "group": "group_1",
    "pickups": [
        {
            "places": [
                {
                    "location": {"lat": 1.3094476, "lng": 103.882367},
                    "duration": 300,
                    "times": [["2021-12-03T04:45:00.000Z", "2021-12-03T04:45:00.000Z"]],
                }
            ],
            "demand": [10, 0, 1],
            "order": 1,
        },
        {
            "places": [
                {
                    "location": {"lat": 1.2828536, "lng": 103.8036075},
                    "duration": 300,
                    "times": [["2021-12-03T04:45:00.000Z", "2021-12-03T12:55:00.000Z"]],
                }
            ],
            "demand": [10, 0, 1],
            "order": 3,
        },
    ],
    "deliveries": [
        {
            "places": [
                {
                    "location": {"lat": 1.363964, "lng": 103.832051},
                    "duration": 300,
                    "times": [["2021-12-03T04:45:00.000Z", "2021-12-03T12:55:00.000Z"]],
                }
            ],
            "demand": [10, 0, 1],
            "order": 2,
        },
        {
            "places": [
                {
                    "location": {"lat": 1.3223009, "lng": 103.9025671},
                    "duration": 300,
                    "times": [["2021-12-03T08:55:00.000Z", "2021-12-03T12:55:00.000Z"]],
                }
            ],
            "demand": [10, 0, 1],
            "order": 4,
        },
    ],
    "value": 20000.0,
}

[reinterpretcat]

Both examples seems correct. However, in the second one you have one extra constraint: if the certain pickup is not possible, then the corresponding delivery is also unassigned.

Also I would remove value property from the jobs and maximize-value objective from objectives in the first example: you have all jobs with the same value and minimize-unassigned objective is also specified, so the value functionality is not needed.

[phat96]

I just checked both examples. The second example is the more precise solution since It would drop whole sequence if some tasks in sequence are not qualified, while the first example don't follow this group/tour constraint.

Thanks you, really appriciate your helps. Keep up with your great works :)