2
$\begingroup$

I have a problem that is similar to the interval scheduling algorithm but it involves priorities. My data sets consist of the following data:

  • Cars with the start and end time of parking, along with their one or more attributes (e.g. electric vehicle, motorcycle, handicapped).
  • Parking spots along with zero or more attributes and lot number.
  • Attributes with their priorities. For example if the property handicapped is given a value of 1, cars that have that attribute should be assigned a parking spot first. Attributes are hard constraints, the priorities of the attributes determine the order of assignment.

There is no overnight parking so I have divided the data into buckets of days. Start and end times are in increments of 5 minutes (not sure if this is important).

To be considered a valid assignment, a car's attributes must be a subset of the attributes for the assigned spot. See examples below.

Objectives

This problem comes from overhauling an existing algorithm, which after observing how users interact with the system, it could definitely use improvement.

My first step is to get something going that can produce one or more possible solutions that meet all of the provided attributes. For example, a limo cannot be assigned to a motorcycle spot. There may not be a complete solution given the inputs, if there are 5 electric vehicles but only 4 spots, the algorithm should still try to assign 4 of them (the 4 that have the highest priority).

Given multiple solutions, the "best" solution would minimize the number of open lots at any given time (ideally all the cars parked in the same lot). Even if it is a small block of time in the middle of the day, the lot can still be closed to minimize the cost of security guards.

Example input/output

Set 1

  • Attributes: [bus: -1; electric: -2; handicapped: -2]
  • Cars: [C1: bus, electric; C2: handicapped, C3: electric]
  • Spots: [P1: bus, electric; P2: bus, electric; P3: electric, handicapped]
  • Valid assignments: [C1-P1, C2-P3, C3-P2] and [C1-P2, C2-P3, C3-P1]

Set 2

  • Attributes: [bus: -1; electric: -2; handicapped: -2]
  • Cars: [C1: bus, handicapped; C2: bus, C3: electric]
  • Spots: [P1: bus, handicapped, electric; P2: bus, electric; P3: handicapped]
  • Valid assignments: [C1-P1, C2-P2, C3-null]

Spot 1 is the only spot that can accommodate car 1. Both cars 2 and 3 can take spot 2 but priority is given to the bus, leaving car 3 unassigned.

Set 3

  • Attributes: [bus: -1; electric: -2; handicapped: -2]
  • Cars: [C1: bus, electric; C2: electric, C3: bus]
  • Spots: [P1: bus, electric; P2: electric; P3: electric, handicapped]
  • Valid assignments: [C1-P1, C2-P2, C3-null] or [C1-P1, C2-P3, C3-null]

There are two buses but only one bus parking spot. Since C1 has a greater priority sum, it is assigned to the available spot even though C3 could have taken it.

Verifying a solution

  1. For each assigned car A, if any, verify the assigned spot (P) that it has been assigned to has all of its attributes. In other words, Attributes(A) is a subset of Attributes(P).
  2. For each unassigned car B, let X be the set of spots in the input data that meet the car's attribute criteria.
    • If one or more spots in X is unassigned, abort these steps and mark the solution as invalid
    • If one or more cars assigned to spots in X has a greater maximum priority than MaxPriority(B), abort these steps and mark the solution as invalid
    • Let Z be the subset of cars assigned to spots in X where the maximum priority of the car = MaxPriority(B). If one or more cars in Z has a greater priority sum than SumPriority(B), abort these steps and mark the solution as invalid

What I have tried

  1. Find all the valid parking spots for each car.
  2. Sort each parking spot list in ascending order of the sum of priorities for the parking spot.
  3. Sort the list of cars in descending order of sum of priorities.
  4. Attempt to assign each car in order of the sorted parking spots. If the spot is taken for that time then try the next one and so on.

I am hoping to make this more efficient by taking into account the interval for each car, as it currently isn't being taken into account when sorting.

I stumbled upon Google Optimization Tools and it looks similar to the nurse scheduling problem but with more constraints. A key difference is that each shift in the NSP is defined whereas the intervals in my problem can partially overlap.

Questions

  1. How can I model the problem?
  2. Are tools like Google OR-Tools or pyschedule appropriate for solving this?
Improve this question
$\endgroup$
12
  • $\begingroup$ FYI, tool recommendation questions are off-topic here. $\endgroup$
    – D.W. ♦
    Commented Apr 2, 2018 at 18:29
  • $\begingroup$ @D.W. I have clarified the output. The attributes are hard constraints. The priorities determine which to assign first, provided that the attributes are met. The number of open lots is a "should", example: given 3 motorcycles and 3 lots with 3, 1, and 1 motorcycle spots respectively, the optimal solution would assign all 3 to the same lot instead of spreading them out. $\endgroup$
    – rink.attendant.6
    Commented Apr 2, 2018 at 21:12
  • $\begingroup$ I don't understand what the hard constraints are, then. What we need is a criteria that, given a proposed assignment, lets us tell whether that assignment is valid. What are those criteria? I don't see them stated anywhere. (We need a criteria that is based solely on the contents of the assignment, not on how it was obtained. In other words, if the criteria is "first assign this, then assign that", that's not useful -- that might be part of the specification of an algorithm, but it's not a requirement that an algorithm must meet.) $\endgroup$
    – D.W. ♦
    Commented Apr 2, 2018 at 21:45
  • $\begingroup$ @D.W. The attributes themselves are hard constraints. To determine whether an assignment is valid, the attributes of each assigned car must be a subset of the attributes of its assigned spot. To determine whether an assignment is valid in the case that not everything can be assigned, the car with the higher priority should be assigned. Should I provide some concrete example inputs/outputs? $\endgroup$
    – rink.attendant.6
    Commented Apr 2, 2018 at 21:55
  • $\begingroup$ It would help if you could state that more clearly in the question. Are you saying that if there exists two cars C,C' such that car C is assigned to a spot, and C' isn't assigned any spot, and C' has higher priority, then the solution is invalid? What if there is no valid assignment where C' receives a parking spot? Is the original assignment still invalid? Also, is that the only kind of hard requirement? The explanation of attributes starts with "For example", hinting that there might be other hard requirements not explained. $\endgroup$
    – D.W. ♦
    Commented Apr 2, 2018 at 22:02

1 Answer 1

Reset to default
0
$\begingroup$

The problem is probably fairly hard. One approach is to formulate it as an instance of integer linear programming. Divide the time period into short time segments. Let $x_{i,j,t}$ be a zero-or-one variable, with the intended meaning that car $i$ is assigned to parking spot $j$ at time segment $t$. Also let $y_i$ be a zero-or-one variable, with the intended meaning that car $i$ is assigned a parking spot (somewhere). Then you can express each of your requirements as a set of linear inequalities on these $x$'s:

  • If car $i$ needs a parking spot for the time window $t_0..t_1$, then add the constraint $\sum_j x_{i,j,t_0}=y_i$, to require that it is assigned exactly one slot if $y_i$ says it should be. Here the sum is over all parking spots $j$ that are compatible with car $i$ (given their attributes).

  • Also, add the constraint $x_{i,j,t_0} = x_{i,j,t_0+1} = \cdots = x_{i,j,t_1}$ for all $j$, to indicate that if car $i$ is assigned to parking spot $j$, then it should be there for its entire time window.

  • To take into account that you can't have two cars parking in the same spot at the same time, add the constraint $\sum_i x_{i,j,t} \le 1$ for all $j,t$.

  • To take into account the priorities, if cars $i,i'$ are both vying for a parking spot at the same time $t$, and if $i$ has higher priority than $i'$ for parking spot $j$, then add the constraint $x_{i,j,t} \ge x_{i',j,t}$. (Add this for all times $t$ in the intersection of their time windows.)

Finally, maximize the objective function $\sum_i y_i$. This is a system of linear inequalities, with a linear objective function, so it can be solved using an off-the-shelf integer linear programming (ILP) solver.

Keep in mind that solving ILP can take exponential time in the worst case, so on large problems, it's possible that the ILP solver might take a very long time. However, the hope is that if your problem is not too large, then an ILP solver might be able to find a good solution in a reasonable amount of time.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.