lab practice :

The application is a ridesharing one to be deployed in any given area of

geographical coverage spanning a city. The environment is specified in the form of a graph structure as

represented below (simply an example; not the entire road network). The graph that you will use

consists of 100 nodes, with an average connectivity of 2 this means setting your p value at 0.02.

Each node in the graph represents either a potential pickup or drop-off point. The distance between a

pair of connected nodes (edge length) is 1 mile. All edges are of the same length. Edges are bidirectional.

For the purposes of this project, we will assume that vehicles travel at a constant speed of 30 mph.

All system operations such as pickup, drop off and van parking can take place at every clock tick which

happens every minute. The only exception is pickup scheduling that occurs every 4 minutes.

All pickups, drop offs and van parking can only occur at nodes, not in-between at edges.

Scheduling

Van Scheduling

The ABC company employs a fleet of vehicles of 30 vans to service the transportation needs of its

customers. Two types of scheduling occur. Firstly, the company assigns a vehicle to a customer based on

proximity of the vehicle to the customers location.

Customer Pickup Order Scheduling

The second type of scheduling is determining the order of pickup of customers from a queue containing

pending requests. The system operates on an internal clock that ticks once every minute. Scheduling of

pickup order happens every 4 minutes on the 4

th clock tick. Up to 3 customers may be scheduled for

pickup depending on the number already in the van. Once a pickup order is determined it will never be

changed at a future point even if a new customer request is at a closer point to the van than any of the

already scheduled pickups.

Each customer enters their pickup point (node number in graph) and drop-off point (also a node

number) when placing a request.

The order is determined by the distance traveled to service the pickups. Suppose for example there is 1

passenger in the van and 5 pending requests are in the queue. Since there is space for 2 more, the first

two requests A and B in the queue (inserted in time arrival order) are removed and examined in terms of

their pickup and drop off locations. If picking up B first and then proceeding to As pickup location is

shorter than first proceeding to As location, then the pickup order will be B first and A second. Likewise,

it will be necessary to determine the pickup order for 3 customers if they are scheduled together at the

same time.

We will also assume that cancellations are not made by either the customer or the company once a

reservation has been made.

Customer Drop off Order Scheduling

Drop offs, just like pickups are scheduled on the basis of distance to be traveled. Drop offs can occur at

any time that there are passengers in the van. Thus, for example, if two requests are serviced to pick up

A and B, then B could be picked up first and then dropped off before As pickup is scheduled. Thus,

pickups can be interspersed with drop offs i.e., drop offs can take place in between pickups.

Van Idling

If a van is not assigned a new passenger after dropping off its last one, then it simply parks at the drop

off point and waits for the next passenger pickup request. We will assume that parking is always

available.

Project Requirements

Part A (due one week after project is handed out)

Your task in this project is to implement the following requirements:

R1. Produce a pseudo code version of the algorithm needed for scheduling customer pickups

R2. Produce a pseudo code version of the algorithm needed to plan a route for passenger drop offs.