Objectives

1. Sort items in a list with respect to a property.
2. Find the shortest paths between given nodes.
3. Develop readable and documented algorithms for business applications.

Scenario

Your team is working on an application for an online shopping company that sells different kinds of products and ships them via cargo companies. The company recently added new product groups to their portfolio, such as grocery and dairy, and began offering privilege programs to their customers, wherein they can get products delivered within a day. They are planning to hire/use their own drivers for such products and customers.

One of your team members is working on transforming data from the streets and addresses of the map to the node and edge structures of a graph. Your ShortestDeliveryPath class will receive the data as nodes, which represent delivery points or intersection of roads, and edges, which represent the roads of the map.

The driver's route will be from the warehouse, which is always node 1, to the first delivery point (node 2), and then from there to the next delivery point, and so on (node n), until all the packages are delivered. Since the application needs to sort deliveries with respect to the due delivery time, the app needs to calculate the shortest path more than once. For this, you will be using the FloydWarshall algorithm to calculate all shortest path pairs at once. You need to modify the FloydWarshall class to store the street names and print the names of the streets on the route.

Details of deliveries will be held in Shipment class. You will be using the deliveryTimeDue variable to set the delivery time limit and the toNode variable to set the delivery node. fromNode is always 1, representing the warehouse from where the driver begins. But in practice, the delivery person will get all packages from the warehouse before beginning work and will deliver each package sequentially. Thus, in practice fromNode will change depending on the location of the delivery person, but this variable does not need to be updated.

Best Practices

1. Get familiar with the FloydWarshall algorithm and its application in this project and add any getters and setters that you need.
2. Get familiar with the Shipment.java class and add any getters and setters that you need.
3. For easy readability, use full variable names instead of short 2-3 character abbreviation.
4. For code reusability, develop separate methods when available.

Tasks

Develop theprintPath(int fromNode, int toNode) method in FloydWarshall class for printing names of the roads on the shortest path form fromNode to toNode.

Add the following methods to the FloydWarshall class:

public String[][] getNameOfStreets() { return nameOfStreets; }

public int[][] getAdjacencyMatrix() { return adjacencyMatrix; }

public int[][] getNextToMatrix() { return comeFromMatrix; }

Develop the getDeliveryRoute(FloydWarshall graph, ArrayList deliveryList) method in ShortestDeliveryPath class as the main method.

Your customer wants you to develop a heuristic optimization method that will find possible delivery stops on the road, provided there is enough time for the remaining deliveries. Using this approach, they want you to check any for possible early deliveries on the route that you previously calculated, within the delivery time limits.

In addition, to avoid confusion, they want the barcode of the package to be printed after the name of the last road that leads to that delivery point. Thus, barcode numbers will indicate when a delivery is to be made while going through the given route. For example: San Carlos St (7654382) 20th St (764256682) Service Rd Winter Pl (2051025601) Winter Pl Rancho Drive (105142566) Spruce Ave (4561378) indicates that deliveries need to be made at San Carlos St, 20th St, Winter Pl, Rancho Drive, and Spruce Ave. The Pseudo Code of the heuristic algorithm is shown in the BonusPsuedocode.java file included in the project.

Use the following formula to calculate the new estimated delivery time:

New Delivery Time = start Time + (length of the route up to the destination) / speed + (number of the stopdeliver points up to destination + 1) x (delivery processing time),