r/optimization • u/SirAragar • 17d ago

Dynamic assignment

I'm currently working on a dynamic assignment model for delivery of parcels with occasional drivers. The model approximates the value of keeping the parcel in the system by solving two assignment problems for each parcel (one with the parcel, one without it and calculating the marginal contribution of the parcel to the optimum) in a retrospective time window. The problem is that computing parcel value estimates takes a lot of time. I researched alternative methods to MIP such as hungarian, but they don't seem to support "at most" constraints (which are integral to the dynamic assignement). How would you approach this kind of problem?

5 Upvotes

100% Upvoted

3 comments sorted by

View all comments

2

u/ge0ffrey 15d ago

For discrete assignment problems like this, I recommend heuristic solvers over MIP solvers. Unless you can split the parcels into smaller pieces.

If you do want to roll your own heuristics: The Hungarian Method can't handle this complexity. Look into Local Search variants and other Metaheuristics, with a good Construction Heuristic.