Given a set of m (>0) trucks and a set of k (>=0) parcels. Each parcel has a fixed amount of payment for the trucks (may be same for all or may different for all) . The problem is to pick up the maximum number of parcels such that the profit of each truck is maximized. There may be 0 to k number of parcels in the service region of a particular truck. Likewise, a parcel can located in the service region of 0 to m trucks. There are certain constraints as follows.
1. Each truck can pick up exactly one parcel.
2. A parcel can be loaded to a truck if and only if it is located within the service region of the truck.
The possible cases are as follows
Case 1. m > k
Case 2. m = k
Case 3. m < k
As far as I know, to prove a given problem H as NP-hard, we need to give a polynomial time reduction algorithm to reduce a NP-Hard problem L to H. Therefore, I am in search of a similar NP-hard problem.
Kindly suggest some NP-hard problem which is similar to the stated problem. Thank you in advance.
Hi:
from your description, your problem looks like the multidimensional knapsack problem. Also reminds me a matching problem. Maybe both are good starting points
David
I'm afraid something is missing here. One truck can carry one parcel only and the it seems (as there are no explicit exclusions) that each parcel can be carried by each truck and the profit doesn't depend on the parcel-to-truck assignment. So, as I can see the problem at the moment., it is needed to sort parcels by profits in the descending order and to assign them to trucks (one parcel to one truck) as long as unloaded trucks are available. Since service regions seem to be separate, the assignments of parcel to trucks should be done for each region separately .
@ Przemysław Kowalik Thank you for your suggestions. A parcel can be loaded to any truck given that it is located in the service region of the truck. The profit does depend on the parcel-to-truck assignment.
P.S. I am not looking for a solution actually trying to prove it NP-Complete.
@ David A. Pelta Thank for this insight, I will see whether these problems can be reduced to mine.
Amar Kaswan, so maybe your problem is a linear assignment problem.
https://en.wikipedia.org/wiki/Assignment_problem
The parameters of the objective function are profits for each possible parcel-truck pair. The objective function must be maximized, of course. If you have an unbalanced case (mk) then you must replace = with
Since each truck can pick up at most one parcel the Problem is "maximum weight bipartite matching" which can be solved in polynomial time, see e.g.
https://en.wikipedia.org/wiki/Matching_(graph_theory).
Let's make sure I understand the problem correctly. Let p_{ij} denote the profit gained if parcel j is loaded onto truck i. If the parcel cannot be loaded onto that particular truck, we just set p_{ij} to zero. Am I right in thinking that we wish to solve the following 0-1 linear program?
maximise
\sum_{i=1}^m \sum_{j=1}^k p_{ij} x_{ij}
subject to
\sum_{i=1}^m x_{ij} \le 1 (for all j)
\sum_{j=1}^k x_{ij} \le 1 (for all i)
x_{ij} \in \{0,1\} (for all i and all j).
If that's right, the problem is very easy. As stated by Przemysław and Helmut, it is equivalent to the linear assignment problem, which in turn is equivalent to maximum-weight bipartite matching.
Yes, but 0-1-LP is NP-Hard whereas Maximum weight bipartite Matching can be done in polynomial time.
Even as LP, it doesn't need to be solved as a binary/integer problem, but just a "standard" LP, since its matrix of parameters of the constraints is totally unimodular and, what follows, all the vertices of the feasible set are integer (0-1 in this case).
I think this similar to parts- machines Grouping problem, or group technology (GT).
- Badges
- Science topic
- Similar topics
- Mathematics