2

In my office, there are 200 employees who come to the office in their car. But my parking space has slots for parking 160 cars only. Now I want to design and develop an application that issues parking tickets to employees by doing a fair allocation of parking slots.

For solving this problem, I was thinking of designing some algorithm like below:

We have 200 employees, 5 working days and 160 available parking slots. Create a pool of 5 colors and assign one color to each of the employees.

  1. 40 - green - Mon, Tue, Wed, Thur
  2. 40 - blue - Tue, Wed, Thur, Fri
  3. 40 - red - Wed, Thur, Fri, Mon
  4. 40 - white - Thur, Fri, Mon, Tue
  5. 40 - black - Fri, Mon, Tue, Wed

With this, we will have only 160 cars coming to the office on any given day.

Now I want to enhance the above algorithm to make this system more effective and efficient for the following use-case:

Employees can apply for a leave, in such cases, his assigned ticket will be unused and parking slot will remain empty - not a very efficient use of the resource. I want to distribute such empty slots to other employees in a fair manner.

What is the most, or at the very least, a more optimal algorithm for solving this?

  • sounds like the scheduling problem developers.google.com/optimization/scheduling/job_shop – Ewan Mar 27 at 18:21
  • 1
    I know you're asking for an addition to your original algorithm, but here's a wild idea: instead of using color codes to distribute space, use an auction. Each month, every employee gets "points" to use in an auction for slots. The 160 highest bidders for a day get a ticket (and pay with their points, so points can't be used twice). When it is known that a slot will be unused for a specific day, the next highest bidder who didn't get a slot gets it. You might even create a market for points so employees without a car can sell points. – Hans-Martin Mosner Mar 27 at 22:10
  • This sound interesting and your approach is sort of gamified way to solve this problem, everyone would love it :) can you please shed more light to this approach, for example how many total points an employee gets for a month and how it will really work? – Lokesh Agrawal Mar 28 at 3:25
  • A separate detailed answer would really help – Lokesh Agrawal Mar 28 at 3:27
  • @Hans-MartinMosner please check my comments above. – Lokesh Agrawal Mar 28 at 3:36
5

It's easier to understand this system if you change the way the color codes are explained:

Blue  = No parking on Mon 
Red   = No parking on Tue  
White = No parking on Wed 
Black = No parking on Thr
Green = No parking on Fri 

Once you see that, this is actually not a complicated problem:

Employees can apply for a leave, in such cases, his assigned ticket will be unused and parking slot will remain empty - not a very efficient use of the resource. I want to distribute such empty slots to other employees in a fair manner.

What is the most, or at the very least, a more optimal algorithm for solving this?

It's Monday and I'm calling in sick. I have a green ticket. Someone with a blue ticket could use it. Pick a blue ticket name out of a hat and give them my green ticket for the day. Done.

If you fear someone wining twice before someone wins once you could switch to a single deck shuffle. It doesn't tip the odds in favor of anyone but it limits how unlucky someone can be. The drawback is it requires you to preserve state.

The lucky winner just has to hope I called in before they got on the bus. Assigning these tickets is easy. Communicating assignment changes is the harder problem to solve.

  • Thanks, this will work, for sake of simplicity I will assume that the people will apply for leaves in advance. I am not sure if picking blue ticket name from hat would be fair or allocating round robin would be fair? – Lokesh Agrawal Mar 27 at 19:14
  • @LokeshAgrawal fair is in the eye of the beholder. But according to the law of large numbers if you work at the company long enough it will be fair if your source of random is fair. Keeping track of who had extra time in the parking lot is unlikely to pay off vs simply using a fair lottery. – candied_orange Mar 27 at 19:23
  • That's true I agree – Lokesh Agrawal Mar 27 at 19:26
  • Pulling out a winner at random is between useless and harmful. France has tried such a lottery system for university applications. It failed, hard. People will think they are treated unfairly: true randomness is only fair for a mathematician. The real life is way more complex, and you have to manage priorities (Alice, who's pregnant, should win the lottery on that blue monday, obviously). This problem is a nightmare to solve "correctly". See also hospital nurses/doctors planning (including part-time management), airline reservation systems. Don't forget laws and regulations. And good luck ;) – Tibo Mar 27 at 20:49
  • @Tibo that's a buy in issue not an algorithmic issue. There are plenty of cases where it works fine. Deer hunting permits, TSA screenings and, well, lotteries. As I said, fair is in the eye of the beholder. – candied_orange Mar 28 at 3:02
3

The Parking Space Auction

Auctions are often used to regulate access to scarce resources, and they are considered a fair mechanism by many people. I'll try to separate mechanism (which is relatively simple) from policy (which may depend on company policies and legal regulations).

This is not a full sketch of the implementation but just a collection of ideas which will need to be fleshed out.

Auction Mechanism

The available parking slots are auctioned for each day sufficiently in advance so that employees can plan their transportation for the day. Employees bid for parking slots using points which are allocated to them in a defined schedule (for example, each employee gets 10000 points at the beginning of a week.)

The auction for each day works like this:

  • While the bidding phase for that day is open, employees place their bids for the respective day. Employees may place bids higher than their current point balance, because they can gain additional points later (see policy options below.) Zero-valued bids are also possible, they just mean the employee would like to take a parking slot if one is available but is not willing to pay for it, for example on holidays when many but not all employees take a day off.
  • When the bidding phase is closed (the auction starts), all bid amounts are clamped to the current balance of the bidder, and bids are sorted by descending amount and ascending timestamps, so that for equal bids the earlier bids win.
  • The first N bids corresponding to the number of parking slots win. You may decide to reduce the amounts on all bids to the minimum winning amount so that all bidders pay the same amount (see policy options below.)
  • Their amount is deducted from the employee's point balance, and the employees each receive a ticket for that day.

Employees may transfer points among each other, for example a group of people sharing a ride may pool their points to get better chances at winning auctions, which makes sense both economically and ecologically. Another option might be for an employee who takes a day off to sell his points to a coworker, or departments might want to hold raffles for points. All of this is up to the users and not part of the auction system.

(Optional) Point Market Mechanism

In addition to being able to transfer points among each other according to direct agreement, employees may sell and buy points on a market embedded in the system. This might enable people who use public transport even if it is a little inconventient to get compensation for that inconvenience, and it might enable higher-paid employees to get better chances at winning an auction by buying points on the market.

Employees may put sell offers and buy orders on the market. Buy orders that are higher than existing sell offers are matched against each other for a transaction.

Policy

There are several possible auction schedules and rules:

  • Daily auction
    The auction for each possible day is held at a specific time in advance, for example at 6 pm two days before. This allows employees to react to unforeseen changes in their needs.
  • Weekly auction
    The auctions for all days of a week are held on Friday or Saturday of the previous week. Each employee receives a summary statement for the days they can use the parking place.
  • Pay lowest winning bid
    Some auctions work so that the winner pays the amount set by the second bid (see https://en.wikipedia.org/wiki/Vickrey_auction) and a possible application to this system would be that all winners of an auction pay just the amount of the minimum winning bid. I am not sure whether this increases or reduces fairness, though.
  • Bid higher than current balance
    Especially when there is sufficient time between making a bid and the respective auction, it might make sense for the employee to bid more than she currently has on balance, because they may get more points in the meantime, for example through the market or due to the regular point schedule when they're taking a vacation and want to bid on auctions for the week after that vacation. However, this may create a wrong perception in other employees about their chances to win an auction.

The company may decide to handle accounts of people with special needs (disabilities, pregnancies, etc.) differently. For example, it may be legally required to make some slots available for people with disabilities, or it may want to give bonus points to pregnant employees to give them better chances at getting a parking slot on each day.

For the point market, it needs to be decided whether it is actually worth the effort (someone has to handle the money involved, which might pose logistical and legal problems.)

Technical Implementation and User Interface

The solution which would probably be easiest for most people would be a website on which employees can log in, see an overview of the open auctions, place their bids and possibly trade points on the market. For many people, a matching smartphone app might be attractive, too.

Tickets could be made available to employees by e-mail or through the smartphone app. Each ticket could contain a QR code with information that can be used by an automated parking barrier to grant access to the parking lot if you have such a barrier.

Scheduling of auctions and point disbursement needs to be implemented using whatever scheduling mechanism is available within the framework you use for the application. You also need scheduling to create auctions for future dates and to clean up past auctions and bids.

The database schema skeleton for the auction part can be relatively simple. You will likely need to add more fields when actually implementing it.

  • Employee
    • e_id (unique key)
    • points (balance of points)
  • Auction
    • date (primary key)
    • slots_available (so you can reduce the number of slots when part of the parking space is unavailable due to construction work or other use)
    • open (flag denoting whether bids can be placed, you might alternatively use a closing timestamp)
  • Bid
    • e_id (key of Employee)
    • date (key of Auction)
    • timestamp (to break ties on equal bids)
    • amount
    • winner (flag denoting whether this bid wins)
  • 1
    Sounds good in theory, but I'm afraid it's going to take too much time off of employees (renewing and following their bids EVERY day). – Kromster Mar 28 at 13:04
  • 1
    @Kromster true, that's why the weekly schedule might be an alternative. It might even be extended to bi-weekly or monthly. There are many other factors which might make such a scheme impractical, it's just a model worth looking at. In the end, the original color coded scheme might be simpler and just as effective. – Hans-Martin Mosner Mar 28 at 13:13
  • @Hans-MartinMosner this sounds amazing, I will definitely evaluate this approach too. Because this has that gamification factor to ir – Lokesh Agrawal Mar 28 at 14:38
  • @Hans-MartinMosner Auction scheme is a bit tricky to design if the auction is happening on a weekly/monthly basis. – Lokesh Agrawal Mar 28 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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