Inventories and driving cars

This week, we had a talk by Amit Sharma, the CTO of Zoomcar as part of the newly initiated industry interaction seminar series. Zoomcar is a self-drive car rental company. The idea is that you can rent a car to drive for a few hours/days. The idea is that you can book a car, pick it up from one of the many pickup points, drive it around and return it to the same point. This is convenient if you want to go out for a drive but don’t own a car. Although there are several such companies in the west, India is only slowly warming up to this idea now.

The main theme of the talk was of inventory management. I found this problem quite interesting, and will attempt to describe a basic version of the same here.

Suppose that we have  K identical items (in this case, cars) in our inventory. Several customers arrive at the store to rent these items for specified durations of time. Customer i arrives at time t_i^{(b)} (booking time) and requests an item for the duration t_i^{(s)} (the start time) to t_i^{(e)} (end time). Note that t_i^{(b)}<t_i^{(s)}<t_i^{(e)}. The problem now is to decide which bookings can be satisfied, and how one can allot the various items to the users. Customer i must be told, immediately upon requesting a booking, whether he can be allocated a car/item or not. The actual allocation of the car/item however can be done anytime before t_{i}^{(s)}. Each booking is associated a certain revenue depending on the duration for which it is booked. For example, a customer booking an item for 2 hours may have to pay more money per hour than a customer booking for a day (discounts for longer durations). To make matters worse, the K items may not be available at all times. For example, some of them may be unavailable from 8 am to 1 pm on Sundays due to a scheduled servicing/maintenance.

The problem sounds simple enough, but there are several challenges. Optimal solutions may exist, but we want an algorithm that runs in real time, and has a complexity as low as possible. For example, listing all the items that are available at any point of time requires a huge storage space, and an algorithm that searches through all of this may require a large overhead. However, just keeping track of the number of items available over time and using this to decide whether items are available or not will not work. To illustrate this, suppose that item 1 is available from 1 pm to 5 pm, and item 2 is available from 3 pm to 9 pm. If we only list the number of items, we see that one item is available from 1 pm to 3 pm, two are available from 3 pm to 5 pm, and one available from 5 pm to 9 pm. Let us now imagine that a user wants an item from 2 pm to 6 pm. We see that the number of items available for this duration is atleast one. However, this request cannot be catered to since no single item is available from 2-6 pm.

There are several other challenges that I have not mentioned here. One can formulate different problems depending on what the variables to be optimized are, and what quantities are to be optimized. For example, only optimizing the revenue may not work, as it may eventually lead to decrease in customer satisfaction. The algorithm must be, in some sense, “fair”. Regular maintenance of items is required, and one can optimize when each item must go for maintenance. In essence, this is an interesting (real-world) problem and good solutions may have a great impact on several areas.