Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Set max number of tasks at vehicle level #421

Closed
NasserEspari opened this issue Dec 29, 2020 · 9 comments · Fixed by #545
Closed

Set max number of tasks at vehicle level #421

NasserEspari opened this issue Dec 29, 2020 · 9 comments · Fixed by #545

Comments

@NasserEspari
Copy link

We are setting 5 as the capacity but the problem is the system is assigning 5 delivery task and 5 pickup task separately which means 10 task at total. Is there any solution for set capacity regardless of task type(pickup and delivery)?

input:

{
  "vehicles": [
    {
      "id": 1,
      "start": [
        2.35044,
        48.71764
      ],
      "end": [
        2.35044,
        48.71764
      ],
      "capacity": [
        1
      ]
    },
    {
      "id": 2,
      "start": [
        2.35044,
        48.71764
      ],
      "end": [
        2.35044,
        48.71764
      ],
      "capacity": [
        1
      ]
    }
  ],
  "jobs": [
    {
      "id": 1,
      "service": 300,
      "delivery": [
        1
      ],
      "location": [
        1.98935,
        48.701
      ]
    },
    {
      "id": 2,
      "service": 300,
      "pickup": [
        1
      ],
      "location": [
        1.98935,
        48.701
      ]
    },
    {
      "id": 5,
      "service": 300,
      "delivery": [
        1
      ],
      "location": [
        1.98935,
        48.701
      ]
    },
    {
      "id": 6,
      "service": 300,
      "delivery": [
        1
      ],
      "location": [
        1.98935,
        48.701
      ]
    }
  ]
}

output:

{
        "success": true,
        "status": 200,
        "data": {
            "code": 0,
            "summary": {
                "cost": 0,
                "unassigned": 1,
                "delivery": [
                    2
                ],
                "amount": [
                    2
                ],
                "pickup": [
                    1
                ],
                "service": 900,
                "duration": 0,
                "waiting_time": 0,
                "priority": 0,
                "computing_times": {
                    "loading": 4,
                    "solving": 1
                }
            },
            "unassigned": [
                {
                    "id": 6,
                    "location": [
                        1.98935,
                        48.701
                    ]
                }
            ],
            "routes": [
                {
                    "vehicle": 1,
                    "cost": 0,
                    "delivery": [
                        1
                    ],
                    "amount": [
                        1
                    ],
                    "pickup": [
                        1
                    ],
                    "service": 600,
                    "duration": 0,
                    "waiting_time": 0,
                    "priority": 0,
                    "steps": [
                        {
                            "type": "start",
                            "location": [
                                2.35044,
                                48.71764
                            ],
                            "load": [
                                1
                            ],
                            "arrival": 0,
                            "duration": 0
                        },
                        {
                            "type": "job",
                            "location": [
                                1.98935,
                                48.701
                            ],
                            "id": 1,
                            "service": 300,
                            "waiting_time": 0,
                            "job": 1,
                            "load": [
                                0
                            ],
                            "arrival": 0,
                            "duration": 0
                        },
                        {
                            "type": "job",
                            "location": [
                                1.98935,
                                48.701
                            ],
                            "id": 2,
                            "service": 300,
                            "waiting_time": 0,
                            "job": 2,
                            "load": [
                                1
                            ],
                            "arrival": 300,
                            "duration": 0
                        },
                        {
                            "type": "end",
                            "location": [
                                2.35044,
                                48.71764
                            ],
                            "load": [
                                1
                            ],
                            "arrival": 600,
                            "duration": 0
                        }
                    ]
                },
                {
                    "vehicle": 2,
                    "cost": 0,
                    "delivery": [
                        1
                    ],
                    "amount": [
                        1
                    ],
                    "pickup": [
                        0
                    ],
                    "service": 300,
                    "duration": 0,
                    "waiting_time": 0,
                    "priority": 0,
                    "steps": [
                        {
                            "type": "start",
                            "location": [
                                2.35044,
                                48.71764
                            ],
                            "load": [
                                1
                            ],
                            "arrival": 0,
                            "duration": 0
                        },
                        {
                            "type": "job",
                            "location": [
                                1.98935,
                                48.701
                            ],
                            "id": 5,
                            "service": 300,
                            "waiting_time": 0,
                            "job": 5,
                            "load": [
                                0
                            ],
                            "arrival": 0,
                            "duration": 0
                        },
                        {
                            "type": "end",
                            "location": [
                                2.35044,
                                48.71764
                            ],
                            "load": [
                                0
                            ],
                            "arrival": 300,
                            "duration": 0
                        }
                    ]
                }
            ]
        }
    }
@jcoupey
Copy link
Collaborator

jcoupey commented Dec 30, 2020

Using a capacity component as a way to cap the number of tasks in a route only works when using job objects. In your situation, if the capacity constraint is only used for this purpose, then you should use only delivery keys (or only pickup keys) so that each job counts as 1 and the vehicle capacity is the max number of jobs in the route. This way you won't have the effect of deliveries and pickups cancelling each other. If you have other "real" capacity constraints, then you should simply add an amount component just for this purpose.

On the other hand, this does not work with shipment objects, and it would be much better to be able to provide a maximum number of tasks in input at vehicle level. In term of implementation, this would require to adjust heuristics and all local search moves to check for excess of tasks in a route. This means quite a number of adjustments but the checks would be pretty straightforward.

@jcoupey jcoupey changed the title set capacity regardless of task type(pickup and delivery) Set max number of tasks at vehicle level Dec 30, 2020
@AnanyDubey
Copy link

@jcoupey, I am a beginner in open source programming and I would like to contribute in this project can you please explain me about this project and how should I proceed further on this issue.

@jcoupey
Copy link
Collaborator

jcoupey commented Jun 4, 2021

@AnanyDubey thanks for your interest. The work outline here would be:

Handle new input

Make sure the new constraint is used during the heuristic process

Heuristics are the way we get initial solutions quickly. We loop through vehicles, then we greedily add tasks into the current route until no more addition is possible.

We'd have to change the "no more addition is possible" to "no more addition is possible or vehicle has reached its max number of tasks". This would happen mostly by adjusting the stopping condition for this while loop.

Make sure the new constraint is used during the local search process

This part is a bit trickier as it requires to dive into the local search process: lookup all existing route modification operators (see this loop) and rule out modifications that would break the max number for one of the vehicles.

For more on how the local search works, you can refer to this SotM talk, it's a bit outdated in term of features but the overall solving process is pretty much still the same.

@cv-or
Copy link

cv-or commented Jul 7, 2021

Hi,

First of all, thanks for creating the Vroom project, it's great!

Quick question: what's the expected timeline for developing this new feature (max number of tasks at vehicle level)?

@jcoupey
Copy link
Collaborator

jcoupey commented Jul 7, 2021

@CosmoVal I'd like to have it included in the next release.

@AnanyDubey you were willing to give this a try, are you still in? No pressure of course, I just want to know if you're still interested.

@AnanyDubey
Copy link

AnanyDubey commented Jul 7, 2021

Sorry @jcoupey actually I have been busy with my college work so I will not be able to attend to the issue.

@torinori
Copy link
Contributor

torinori commented Jul 9, 2021

Hi!
Added constraint in heuristics process.

How I understand, every operator has .is_valid() method, should I add this constraint in to it?

@jcoupey
Copy link
Collaborator

jcoupey commented Jul 9, 2021

every operator has .is_valid() method, should I add this constraint in to it?

That would be a way to do it but is_valid is only called once we have created the operator object, computed the associated gain and decided whether we want to check validity with regard to more complex stuff (capacity, time windows). On the other hand, deciding whether a given move will break the "max task number" constraint is really straightforward, so it would be more efficient to filter out the violations beforehand.

This means that for all operators tested in this loop, we have to early abort the search based on the current number of tasks in source/target routes, and the move.

For example to prevent trying relocating a job to an already full target route:

// Relocate stuff
for (const auto& s_t : s_t_pairs) {
if (s_t.first == s_t.second or best_priorities[s_t.first] > 0 or
best_priorities[s_t.second] > 0 or _sol[s_t.first].size() == 0) {
continue;
}

we should add a condition along the line of _sol[s_t.second].size() == max_value_for_target_route.

@bottorezhan that's great if you're willing to move forward on this! In that case, could you fork the repo and open a PR so we could move the technical talk there?

@torinori
Copy link
Contributor

torinori commented Jul 12, 2021

HI!

Are there any explanations for the rest of the operators, besides these 6?

operators

Also, does it true that all intra-operators doesn't change the size of the route ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

5 participants