Figure B.1B.1B.1: Illustration of sample input. Scheduled trips are depicted by dashed red lines with their respective start times. The optimal solution is to have one driver complete the trip from 222 to 333 at time 000, then travel to location 111 arriving at time 888, and then complete the trip from 111 to 222. The second driver can complete the trip from 333 to 444.
Jamal owns a new ride-hailing business. His business operates in the following way: At least 121212 hours before a trip is desired, a customer orders a trip from a starting location to an ending location to take place at a specified starting time. Although Jamal has considered ride-sharing in the past, due to the ongoing pandemic, each ordered trip is currently completed before another begins. Jamal’s company has a layout of the current service area and upper bounds for the time required to drive any particular road. At some point, the team would like to incorporate traffic data to make the map dynamic, but at the moment fixed costs are what we have to work with. By having each trip scheduled in advance, Jamal’s company is able to optimize route-planning and provide an attractive business model for drivers. His company does this in the following way: Every 888 hours, Jamal selects a set of drivers to work a shift picking up and dropping off customers according to their desired schedules. Drivers are then paid per shift worked, rather than per trip completed. Jamal has found this model to be more satisfactory to drivers compared to current ride-hailing businesses. In current businesses, drivers face uncertainty as to how many rides they will be able to procure, and thus how much money they will earn. Jamal’s business, on the other hand, pays drivers for every shift they work, and so a driver will either be earning money (if they work a shift) or be free to occupy their time by other means (if they aren’t needed for a shift), instead of waiting around in their car hoping for a passenger to request a ride. Unfortunately, Jamal is more of a business-type and needs help with coding for his company. In particular, he is lacking the algorithm to determine given a set of ordered trips in an eight-hour window, the minimum number of drivers that should be hired for the given shift. Can you help Jamal with this crucial task? Figure B.1B.1B.1: Illustration of sample input. Scheduled trips are depicted by dashed red lines with their respective start times. The optimal solution is to have one driver complete the trip from 222 to 333 at time 000, then travel to location 111 arriving at time 888, and then complete the trip from 111 to 222. The second driver can complete the trip from 333 to 444.
