MUPHORIA
Do you enjoy solving problems?
Do you like flaunting your programming skills?
Wanna do this by being part of a category defining company
Do you like flaunting your programming skills?
Wanna do this by being part of a category defining company
Participate in MuPhoriaTM. Win upto Rs.6
Lakhs* and a chance to work with Mu Sigma!
Although the contest is now over, I want to give a brief
introduction of this contest along with my submission:
PURPOSE
MuPhoria (the “Contest”) was designed
to:
1.Create awareness
about the Decision Sciences industry.
2.Encourage and
inspire students to gain exposure to real world business problems.
3.Provide students
an opportunity to innovate by integrating Math, Business and Technology.
I too partcipated
in MUPHORIA and got selected in top five thrice thereby secured an interview
with MU Sigma.
The problem
was to find the shortest routes for a set of vehicles so as to minimize the
total cost for three years.
Although I
tried best but my solution was not so great. Here goes my solution for the
concerned problem:
Business
logic class: Muphoria
//Muphoria.java import java.io.FileReader; import java.io.FileWriter; import java.io.LineNumberReader; import java.util.ArrayList; import javax.swing.JOptionPane; /** * * @author VIKASH MAYANK */ public final class Muphoria { /** * instance variables * */ private long total = 0;//stores total distance travelled private String storeDcMatrix[][] = new String[602][602];//2D array to store the distance among stores and distribution centre containing first row of stores name also private int distanceSheetMatrix[][] = new int[601][601];//2D array to store distance among store and distribution centre i.e an array containg 601 rows and 601 columns private String storeWeightMatrix[][] = new String[600][2];//stores store name and their respective demand private int weightSheetMatrix[] = new int[600];//this array contains only demands of all the 600 stores private Store[] stores = new Store[600];//this array contains store information private ArrayList<Truck> truckList = new ArrayList<Truck>();//an arraylist containing list of trucks private ArrayList<Integer> deliveredStoreindexList = new ArrayList<Integer>();//this arraylist stores index of store where goods have been delivered private boolean flag = true;//this becomes false as soon a store is served private FileWriter fileWriter;//writes csv(comma separated values) file private int adjustmentFactor = 1000;//determine the maximum goods delivered by a truck so that adjustStore(-,-,-) method can be called... private String sheet1 = "";//get sheet1.csv private String sheet2 = "";//get sheet2.csv /** * constructor */ public Muphoria(String sheet1, String sheet2) { this.sheet1 = sheet1; this.sheet2 = sheet2; readData(); }//constructor-----end----- /**reads data from comma delimited csv file * */ private void readData() { try { FileReader file = new FileReader(sheet1);//gets file LineNumberReader lnr = new LineNumberReader(file);//reads one line at a time //skip four lines of csv file to start reading data lnr.readLine(); lnr.readLine(); lnr.readLine(); lnr.readLine(); //read csv file line by line and store data in storeDcMatrix for (int i = 0; i < 602; i++) { //read one line String string = lnr.readLine(); //split the string on the basis of comma(,) as a regular expression storeDcMatrix[i] = string.split("[,]"); } file = new FileReader(sheet2);//get dataSheet2 lnr = new LineNumberReader(file); //skip two lines lnr.readLine(); lnr.readLine(); //stores store and their respective demand in storeWeightMatrix for (int i = 0; i < storeWeightMatrix.length; i++) { //read a line String string = lnr.readLine(); for (int j = 0; j < storeWeightMatrix[i].length; j++) { storeWeightMatrix[i] = string.split("[,]");//split the string and return values... } } } catch (Exception e) { System.err.println("System can not find the file specified...\nMake sure...\na)sheet1.csv and sheet2.csv are in the current directory...\nb)Please take a look at readme.pdf document for setup instructions..."); javax.swing.JOptionPane.showMessageDialog(null, "System can not find the file specified...\nMake sure...\na)sheet1.csv and sheet2.csv are in the current directory...\nb)Please take a look at readme.pdf document for setup instructions...", "Error Occured!", JOptionPane.ERROR_MESSAGE); System.exit(0); } //transferring string array(storeDcMatrix) values into int array(distanceSheetMatrix) for (int i = 0; i < distanceSheetMatrix.length; i++) { for (int j = 0; j < distanceSheetMatrix[i].length; j++) { if (i + 1 == j + 1) { distanceSheetMatrix[i][j] = 0;//put zero as distance of a store from itself is zero } else { /**To avoid weird behaviour of floating arithmetic... * We have multiplied distance by 100 here and casted the data into int type so as to ease calculation part ... * This does not affect the calculation and actual output because the 65 km distance limit has been checked properly ... */ distanceSheetMatrix[i][j] = (int) (Float.parseFloat(storeDcMatrix[i + 1][j + 1]) * 100);//distanceSheetMatrix contains distance only, storeDcMatrix contains name of the store as well } } } //get demand of 600 stores in stores array as well as in weightSheetMatrix for (int i = 0; i < 600; i++) { weightSheetMatrix[i] = Integer.parseInt(storeWeightMatrix[i][1].trim()); stores[i] = new Store(); stores[i].setDemand(Integer.parseInt(storeWeightMatrix[i][1].trim())); } }//readData()--------------end------------------- /** * getResult() method changes the value of adjustmentFactor which determines the minimum amount of goods so that * a truck can adjust its store by making a calll to adjustStore(-,-,-) method. * * This determines the best value of adjustmentFactor so that total cost over three year is minimum... */ public void getResult() { //make a new Muphoria class object(adjustmentFactor is by default 1000) Muphoria muphoria = new Muphoria(sheet1, sheet2); muphoria.readData();//read data from csv files... muphoria.process();//process the result... muphoria.calculateTotalCost();//calculate total cost //loop again and again determine the best adjustmentfactor for ehich total cost over three year is minimum... for (int i = 1000; i > 900; i--) { truckList.clear();//clear the current truckList... deliveredStoreindexList.clear();//clear the deliveredStoreIndexlist.. for (int j = 0; j < stores.length; j++) {//set status of every store to true... stores[j].setStatus(true); } adjustmentFactor = i;//set the new adjustmentFactor flag = true;//set flag true... this.process();//process result... this.calculateTotalCost();//calculate total cost considering new adjustment factor... if (total < muphoria.total) {//if total cost for this adjustment factor is minimum then store the truckList and total cost in muphoria(object of Muphoria class)... muphoria.total = total;//set new total cost muphoria.truckList.clear();//clear muphoria object truckList for (Truck t : truckList) { muphoria.truckList.add(t); } } } muphoria.generateOutput();//generate the best output... System.out.println("output.csv file is generated in the current directory!"); javax.swing.JOptionPane.showMessageDialog(null, "output.csv file is generated in the current directory!", "Output Generated", JOptionPane.INFORMATION_MESSAGE); }//getResult()--------------end---------- //find the total number of truck needed... private void process() { int j = 1; while (deliveredStoreindexList.size() < 600) { Truck truck = new Truck(j); truckList.add(truck); flag = true; findRoutes(truckList.get(j - 1)); // truckList.add(truck); j++; } }//process()--------------------end--------------- //calculate total cost... private void calculateTotalCost() { total = 0; //calculate total distance travelled for (Truck truck : truckList) { total += truck.getDistance(); } total = (total * 30 * 365 * 3) / 100;//cost of travel for three year... total += truckList.size() * 20000 * 12 * 3;//total cost over three year... }//calculateTotalCost()----------------end------------- //generate output.csv file... private void generateOutput() { int maximumSore = 0; total = 0; //find the maximum number of store delivered by a truck... for (Truck truck : truckList) { total += truck.getDistance(); if (maximumSore < truck.getPath().size()) { maximumSore = truck.getPath().size(); } } try { fileWriter = new FileWriter("output.csv", false);//create a output.csv file fileWriter.write(" Total truck needed : " + truckList.size() + "\n Total distance travelled each day(in km) : " + (float) total / 100.0f + "\n"); calculateTotalCost(); fileWriter.write(" Total cost over three years : " + total + "\n"); fileWriter.write("\n DC : Distribution Centre (DC is not a stop)\n"); fileWriter.write("\n Routing for each truck \n\n"); fileWriter.close(); //this for loop write name of each truck in output.csv file... for (Truck truck : truckList) { fileWriter = new FileWriter("output.csv", true); fileWriter.write(truck.getName() + ","); fileWriter.close(); } //write route of each truck... for (int i = 0; i < maximumSore; i++) { fileWriter = new FileWriter("output.csv", true); fileWriter.flush(); fileWriter.write("\n"); for (int j = 0; j < truckList.size(); j++) { Truck truck = truckList.get(j); if (truck.getPath().size() > i) { fileWriter.write(truck.getPath().get(i) + ","); } else { fileWriter.write(","); } } fileWriter.close(); } } catch (Exception e) { System.err.println("can not generate output file...\nMake sure...\n1)The output.csv file is not being used by another process.\n2)Current directory has sufficient file write permission..."); javax.swing.JOptionPane.showMessageDialog(null, "can not generate output file...\nMake sure...\n1)The output.csv file is not being used by another process.\n2)Current directory has sufficient file write permission...", "Error generating file!", JOptionPane.ERROR_MESSAGE); System.exit(0); } }//generateOutput()----------------------end--------- //finds the route of trucks private void findRoutes(Truck truck) { Store store = new Store(); int index = 0; int demand = 0; int distance = 0; // while(-) runs until all the stores are visited while (flag) { if (deliveredStoreindexList.size() == 600) { flag = false; break; } if (truck.isStatus()) { if (truck.getIndex().size() == 0) { // get nearest store from distribution centre store = getNextStore(distanceSheetMatrix[600]); truck.addPath("DC"); } else { //get store nearest to previous store store = getNextStore(distanceSheetMatrix[truck.getIndex().get(truck.getIndex().size() - 1)]); } //get details of nearest store index = store.getIndex(); demand = store.getDemand(); distance = store.getDistance(); //update truck truck.addDistance(distance); truck.addIndex(index); truck.setDelivered(demand); truck.setTime(); store.setStatus(false); /**if goods delivered exceeds 1000 kg or * time spent exceeds 10800 seconds =3 hours or * distance travelled + return distance exceeds 65km then remove the last updated record * */ if (truck.getDelivered() > 1000 || truck.getTime() > 10800 || (truck.getDistance() + distanceSheetMatrix[600][index]) / 100 > 65) { store.setStatus(true); truck.getIndex().remove(truck.getIndex().size() - 1); distance = -distance; truck.addDistance(distance); demand = -demand; truck.setDelivered(demand); truck.setTime(); //adjust the last store with a new store where goods to be delivered is less than required to complete 1000 kg if (truck.getDelivered() < adjustmentFactor) { store = adjustStore(distanceSheetMatrix[truck.getIndex().get(truck.getIndex().size() - 1)], 1000 - truck.getDelivered()); //get details of nearest store index = store.getIndex(); demand = store.getDemand(); distance = store.getDistance(); //update truck truck.addDistance(distance); truck.addIndex(index); truck.setDelivered(demand); truck.setTime(); store.setStatus(false); deliveredStoreindexList.add(index); } //set truck status false truck.setStatus(false); //add return distance truck.addDistance(distanceSheetMatrix[600][truck.getIndex().get(truck.getIndex().size() - 1)]); //time exceeds 3 hours then remove the last updation if (truck.getTime() > 10800) { store.setStatus(true); truck.getIndex().remove(truck.getIndex().size() - 1); distance = -distance; truck.addDistance(distance); demand = -demand; truck.setDelivered(demand); truck.setTime(); deliveredStoreindexList.remove(deliveredStoreindexList.size() - 1); } // distance travelled exceeds 65 km then remove the last updation if ((truck.getDistance() / 100) > 65) {//truck.getDistance() is divided by 100 as we originally multiplied each distance by 100 in distanceSheetMatrix store.setStatus(true); truck.getIndex().remove(truck.getIndex().size() - 1); distance = -distance; truck.addDistance(distance); demand = -demand; truck.setDelivered(demand); truck.setTime(); deliveredStoreindexList.remove(deliveredStoreindexList.size() - 1); } flag = false; truck.addPath("DC"); } else { //add visited store name in path truck.addPath(storeDcMatrix[0][index + 1]); //update deliveredStoreindexList deliveredStoreindexList.add(index); } //add return distance of the truck if all the stores are visited if (deliveredStoreindexList.size() == 600 && truck.getIndex().size() < 35 && truck.getDelivered() <= 1000) { truck.addDistance(distanceSheetMatrix[600][truck.getIndex().get(truck.getIndex().size() - 1)]); flag = false; truck.addPath("DC"); } //set truck status false if 35 stores are served ... if (truck.getIndex().size() == 35) { truck.setStatus(false); truck.addDistance(distanceSheetMatrix[600][truck.getIndex().get(truck.getIndex().size() - 1)]); flag = false; truck.addPath("DC"); } } }//while end ... }//findRoutes()------------end----------- //getNextStore(-,-,-) finds the nearest store from the previously visited store private Store getNextStore(int[] prevStore) { int index = 0; int distance = 0; //find store where goods have not been delivered... for (int i = 0; i < 600; i++) { if (prevStore[i] != 0 && stores[i].isStatus()) { index = i; distance = prevStore[i]; stores[i].setIndex(index); stores[i].setDistance(distance); break; } } //find the nearest store where goods have not been delivered... for (int i = 0; i < 600; i++) { if (prevStore[i] != 0 && (prevStore[i]) <= distance && stores[i].isStatus()) { distance = prevStore[i]; index = i; stores[i].setIndex(index); stores[i].setDistance(distance); } } //return the nearest store return stores[index]; }//getNextStore(-)-------------end------------ /**called when the last nearest store has more demand of goods than goods that can be delivered by the truck keeping 1000 kg limit * this method takes input as previous store and required goods in the truck and returns the store having highest demand of goods(less than required goods)... */ private Store adjustStore(int[] prevStore, int required) { int index = 0; int distance = 0; int weight = 0; //finds a store which is not visited... for (int i = 0; i < 600; i++) { if (prevStore[i] != 0 && stores[i].isStatus() && weightSheetMatrix[i] < required) { index = i; distance = prevStore[i]; weight = weightSheetMatrix[i]; stores[i].setIndex(index); stores[i].setDistance(distance); break; } } //finds the store having highest demand of goods(less than required)... for (int i = 0; i < 600; i++) { if (prevStore[i] != 0 && (weightSheetMatrix[i]) >= weight && weightSheetMatrix[i] < required && stores[i].isStatus()) { distance = prevStore[i]; weight = weightSheetMatrix[i]; index = i; stores[i].setIndex(index); stores[i].setDistance(distance); } } return stores[index]; }//adjustStore(-,-)----------------------end--------------- }//Muphoria-------------------business logic class-------------- // class Store { private int distance;//distance of a store from previously visited store(dynamically changes as the previously visited store changes)... private int demand;//demand of goods... private int index;//index position in array... private boolean status;//becomes false as soon as goods have been delivered... public Store() { status = true; } public boolean isStatus() { return status; } public void setStatus(boolean status) { this.status = status; } public int getDemand() { return demand; } public void setDemand(int demand) { this.demand = demand; } public int getDistance() { return distance; } public void setDistance(int distance) { this.distance = distance; } public int getIndex() { return index; } public void setIndex(int index) { this.index = index; } }//Store-------business logic class------------ // class Truck { private boolean status = true;//status becomes false as soon as any constraints like time limit ,maximum goods that can be delivered or maximum distance that can be travelled tends to be invalid private int distance;//total distance travelled... private ArrayList<string> path = new ArrayList<string>();//keep track of stores where goods have been delivered... private ArrayList<Integer> index = new ArrayList<Integer>();//keep track of index of stores in array private int delivered;//total goods delivered... private int time;//time spent... private String name;//name of the truck... public Truck(int number) { setName("Truck#" + number); } public int getDelivered() { return delivered; } public void setDelivered(int delivered) { this.delivered += delivered; } public String getName() { return name; } private void setName(String name) { this.name = name; } public int getTime() { return time; } public void setTime() { //aeach truck can travel upto 3 hours to deliver goods i.e. 60*60*60=10800 seconds int seconds = 0; //add total time taken to travel the distance seconds += getDistance() * 90 / 100; //add 5 minutes =5*60 = 300 seconds for each stop seconds += getIndex().size() * 300; this.time = seconds; } public int getDistance() { return distance; } public void setDistance(int distance) { this.distance += distance; } public void addDistance(int distance) { this.distance += distance; } public ArrayList<Integer> getIndex() { return index; } public void setIndex(ArrayList<Integer> index) { this.index = index; } public void addIndex(int index) { this.index.add(index); } public ArrayList<string> getPath() { return path; } public void setPath(ArrayList<string> path) { this.path = path; } public void addPath(String path) { this.path.add(path); } public boolean isStatus() { return status; } public void setStatus(boolean status) { this.status = status; } }//Truck---------------business logic class-------------
//Main.java public class Main { public static void main(String[] args) { Muphoria muphoria=new Muphoria("sheet1.csv","sheet2.csv"); muphoria.getResult(); } }//Main---------execution logic class-------
Can share you the problem statement of Muphoria 2012 . I tried googling but i didnt find any.Please respond soon.Thanks in advance
ReplyDeletePROBLEM STATEMENT
DeleteGroceryKart.com is responsible for supplying fresh vegetables and produce to all mom-and-pop retail stores in Mumbai and adjoining suburbs. There are about
600 stores in their network. They have a fleet of old Matador vans that are being used to haul the goods from their central warehouse in Andheri. Given the
perishable nature of the goods, all vans leave at 5:00 AM and all deliveries have to happen before 8:00 AM. Each van can make multiple stops but the union contract
prevents any truck from making more than 35 stops or travelling more than 65 KM in any trip.
In an effort to reduce costs and minimize greenhouse emissions, GroceryKart.com is planning to retire all the old Matador vans and purchase a new fleet of
Mahindra vans. They believe the cost of purchasing the Mahindra vans will more or less be covered by the sale of Matador vans and the rest of the money will come
from the existing savings fund. However, maintaining each truck costs Rs. 20,000 a month (including driver, etc.). Also, the variable cost/km of travel is around Rs.
30 for the first three years of the truck usage. Each Mahindra truck can carry up to 1000 kg at full capacity and at the end of the trip, all trucks return back to the
warehouse. Each stop at the store takes 5 minutes to download (irrespective of the weight) and every KM travelled takes 90 seconds on an average.
The distance between each store and the warehouse is provided in Table 1. The daily demand for each store is provided in Table 2. (Click here to download the
dataset)
Can you write a program to determine the number of Mahindra vans required to be purchased and the total KM that will be travelled to service the daily demand of all
the stores so as to minimize the total cost over the first three years?
The output of the code should clearly mention:
The number of trucks needed
Routing for each truck and
The total miles travelled each day
The output should be in a csv where every column of the output is a truck and the entries in the column correspond to the stops the truck makes.
how could you write such a lengthy code?...have you used SAS software?
ReplyDeleteNo, I used simply notepad++.
Deletecan you also share the dataset to help us understand it?
ReplyDelete