WIB1002编程辅导、写作Java，c++程序

” WIB1002编程辅导、写作Java，c++程序WIA/WIB1002 DS Assignment (S2, 2020/21) Always on Time Delivery1Always On Time DeliveryIntroductionYour friends delivery company Never On Time Sdn Bhd is receiving tons of complaints fromcustomers as they feel that the delivery process is far too slow. Delivery men in your friendscompany are always lost in the middle of their delivery route, dont know where to deliver theparcel and which road they should take to shorten the delivery time. Sometimes they feel angryand exhausted when they lose their direction and they eventually take it out on the parcelswhich causes more complaints From customers. Your friend tried out many ways to solve theproblem but to no avail. Hence, you are your friends last hope to save his company.Figure 1: Visualization of the problems underlying structureProblem StatementIn this assignment, you as a professional engineer are requested to simulate the deliveryprocess and planning in a country to help your friend shorten their delivery time.Basic RequirementsLet us start with definitions of all terms we are going to use in this problem context. A customeris an entity that has a certain demand and therefore requires the presence of a vehicle, a unitthat can move between customers and the depot, a unit that initially possesses the demandsof the customers. All vehicles are capacitated that they can only contain goods (the customersdemands) up to a certain maximum capacity. Moving a vehicle between the depot and thecustomers comes with a certain cost. A route is a sequence of visited customers by a certainvehicle, starting and ending at a depot while a tour is a list of routes of all vehicles to fulfil allcustomers demands.You can imagine the underlying structure of this problem as a complete undirected graphG(V, E). A simple visualization is given in the Fig. 1 above.WIA/WIB1002 DS Assignment (S2, 2020/21) Always on Time Delivery2InputGiven a text file, where the first row indicates the number of customers (including depot),N and maximum capacity of all vehicles, C. After this, starting from second row onwardsare the N rows of information. In particular, every row of information contains 3 data, whichare x-coordinate, y-coordinate and lastly demand size of a customer. The second rowrepresents the depot and its demand size is always 0 while the rest of the rows show customerinformation. An example of input is given below.Figure 2: The format of the input file and the example input.In Fig. 2, the left side of the figure shows the input file format, while the right side of the figureshows an example of input text file. In this example, N=5 indicates that there are 4 customersand a depot, and the maximum capacity for all vehicles you use is 10.It is then followed by 5 rows of information. Second row of the example input indicates locationof the depot in x and y Coordinates, (86, 22) and demand size is 0. The next 4 rows (viz., thirdrow to sixth row) show locations and demand size of every customer. For instance, the firstcustomer is located at (29, 17) with demand size of 1. In order for us to identify depot andevery customer, we simply give each one of them an ID according to their sequence in thetext file. For example, the depot located at (86, 22) is assigned an ID of 0, then the firstcustomer located at (29, 17) with demand size 1 is assigned an ID of 1, followed by ID 2 forsecond customer at (4, 50) with demand size 8, etc.Noted that Fig. 2 is only an example input, you may adjust input format for your own needs.Given any input of this format, your task is to find out the best tour with lowest cost (a tourscost is simply the summation of all routes costs while a routes cost is simply the totalEuclidean distance travelled by the vehicle using that route). Note that this also means thatyour program needs to find out what is the best number of vehicles to be used as well in orderto achieve the lowest cost.WIA/WIB1002 DS Assignment (S2, 2020/21) Always on Time Delivery3OutputThere are total of 3 outputs you have to generate, we define each output as a simulation:1. Lets start with a simple one. In the first simulation, you are requested to find the besttour for a given case with small N using Breadth-First Search / Depth-First Searchtraversal implementation which you will learn in the class. We name this approach asBasic Simulation.2. Secondly, you are requested to implement a Greedy Search that is able to find a goodsolution given a case with small or large N. Greedy Search means we simply look forthe best option in the next move when we travel through the whole graph. Forillustration, in this context the vehicle will always looks for the shortest distancebetween current location and all next possible location to select the next location to go.A simple explanation will be Given in the Github link provided in Resource section. Wename this approach as Greedy Simulation.3. Now, this is the most important part of this simulation. We want to search for the besttour that we could search of in a limited computation time. This means that if weare given enough time, then we will provide the best tour else we will just provide thebest tour we could find of if we are given a limited time with large N. Thus, we are goingto implement another searching algorithm, which is known as Monte Carlo TreeSearch. A brief explanation of this algorithm is given in the next section. We name thisapproach as MCTS Simulation.For every simulation, you need to show the tours cost, followed by every used vehiclesinformation which includes the route taken, vehicles used capacity and cost of the routetaken. Sample output is given below with the case of the sample input given in the previoussection.Figure 3: Example output based on the input file in Fig. 2. You may output your simulationsone after another instead of side by side. It is put as side by side here just to save spaces.WIA/WIB1002 DS Assignment (S2, 2020/21) Always on Time Delivery4Monte Carlo Tree SearchIn MCTS, nodes are the building blocks of the search tree. These nodes are formed based onthe outcome of a number of simulations. In general, MCTS selects next moves based oncertain strategies until the end (leaf node), and based on the evaluation of the status in leafnode, we backpropagate the evaluation result to the root node to update the strategy so thatwe can select a better move in next loop. The process of Monte Carlo Tree Search can bebroken down into four distinct steps, selection, expansion, simulation, and backpropagationas shown in the figure below.Figure 4: The Monte Carlo Tree Search process.● Selection: In this process, the MCTS algorithm traverses the current tree from the rootnode using a specific strategy. The strategy we are going to use to solve our problemis policy adaptation. It is a bit long to be explained here and out of the scope of thisData Structure course thus the full logic of selection will be provided. Based on thepolicy, we select the best child from all possible child nodes and enter the expansionphase.● Expansion: In this process, a new child node is added to the tree to that node whichwas optimally reached during the selection process.● Simulation: In this Process, a simulation is performed by choosing moves or strategiesuntil a result or predefined state is achieved. We can choose those moves randomly,to perform a random simulation, but for better efficiency, we choose the movesaccording to policy.● Backpropagation: After determining the value of the newly added node, the remainingtree must be updated. So, the backpropagation process is performed, where itbackpropagates from the new node to the root node. During the process, the policy weuse to select moves is updated according to the cost of the result.For your knowledge, MCTS was indeed successfully implemented in many real lifeapplications such as board games including Chess and Go (AlphaGo), protein foldingproblems, chemical design applications, planning and logistics, building structural design,interplanetary flights planning and is currently intended as one of the best approaches inArtificial General Intelligence for games (AGI).WIA/WIB1002 DS Assignment (S2, 2020/21) Always on Time Delivery5ResourcesI uploaded some of the sample inputs on my personal GitHub repository, where you canaccess it through this link: Delivery-Instances (GitHub Repo). You might want to test yourprogram using the sample inputs provided there or you can simply generate inputs randomlyfor your own sake. The sample inputs provided there follow the input format explained earlierand if your program is receiving a different input format then you might need to change thosesamples format after downloading them as well.Inside the repository you will also find the implementation of MCTS, in pseudo-codes form,and I believe you guys have the ability to figure out the complete implementation.If you have any questions please feel free to raise it in the GitHub repo by creating a new issue.I will check the repo from time to time and try to answer your questions. If you are unfamiliarwith GitHub, here is a documentation guide on how to create a new issue in a GitHub repo.Extra: I might be putting more and more resources regarding the problems (some possiblenew ideas for extra features of this problem or explanations about MCTS as well) for yourreading. If you are interested, can try checking the GitHub repo from time to time.WIA/WIB1002 DS Assignment (S2, 2020/21) Always on Time Delivery6Extra FeaturesGraphic User Interface (GUI)Build your simulator with a nice looking GUI. You can either simulate it in a graph or in a graphwith a graphic map background. Your program should simulate the process of delivery(movement of vehicles between locations with respect to time).Random Parcel Pick Up SpawningDuring the parcel delivery Process, there might be customers requesting parcel pick up fromtheir home to be delivered to other places. Thus, in order to minimize cost, we have to updatethe path used by couriers (vehicles) whenever there is a new request for parcel pickup from anew location.Pickup and DeliveryIn this case, parcels are not initially located at the depot, instead parcels are on the customerssite. For every customer, you need to send a vehicle to their location to pick up the parcel(demand) and send it to another location specified by the customer (demand is released indestination).There are few things you might need to be careful of: first, a delivery point cannot come beforeits respective pickup point when you find the best route for your couriers. Secondly, all vehiclesdeparting from the depot have 0 used capacity (as parcels are not inside the depot anymore).When a vehicle reaches a pickup point, it decrements the available capacity in the vehicle asit pickups the parcel. When a vehicle reaches a delivery point with its respective parcel, itreleases the parcel and thus increments back the available capacity of the vehicle.Heterogeneous Vehicle CapacityIn basic requirements, we assume that every vehicle shares the same capacity, C. In fact, wemight have different types of vehicles that have different capacity (e.g. a lorry can deliver moreloads than a van). In order to produce a simulation closer to real life, you might need toconsider adding this feature.Time constraint from customerIn real life, we not only have to minimize the time and fuel (represented by distance) used bycouriers, we also have to consider the expected arrival time of every parcel to their owners.We should not deliver the parcel later than its expected arrival time as it would result in badcustomer reviews. In your simulation, you might want to add this feature as well.For every customer, you might need to add a time window [t1, t2] to specify the time range wecan deliver a parcel to a customer. If we arrive at the customer location before t1, then wehave to wait for it and do nothing Else, and if we deliver the parcel after t2, then we will receivea penalty which is undesired. Thus, your tour should strictly follow the time window for everycustomer and at the same time minimize the cost.WIA/WIB1002 DS Assignment (S2, 2020/21) Always on Time Delivery7Traffic ConditionsTraffic conditions for every road keep changing due to many reasons which we cant predict(accidents, peak hours, holiday seasons etc.). In your simulation, you can also simulate thisby assigning flexible time (that may change from time to time) to every road (connectionbetween nodes). When there are traffic condition changes, the path taken by every courierthat is affected should make some changes as well.Site-Dependent CustomerNot every type of vehicle can serve every type of customer because of site-dependentrestrictions. For example, customers located in very narrow streets cannot be served by a verybig truck, and customers with very high demands require large vehicles. So associated witheach customer is a set of feasible vehicles but not all.Extra Algorithm ImplementationYou can implement other searching algorithms to search for a best-known path for the deliveryprocess. Here are some of the possible searching algorithm you might want to consider:1. Best First Search2. A* Search3. Genetic Algorithm4. Hybrid Search I (MCTS + GA)5. Hybrid Search II (MCTS + ML)6. Your custom searching algorithmParallelism (Threading)You might want to apply parallel programming for the MCTS algorithm. For MCTS, simulationsmade can be run parallelly to reduce time usage greatly so that we can get a better result withshorter time for large N.You can also apply parallel programming by parallelising the process of vehicle movementand route searching. You can try to search a best next move first using MCTS, then whilevehicle is moving to the next location (which the process should take some times if you animateyour simulation), you can continue to search the next best move from the next location so thatyou dont have to waste so Much time initially for searching the best whole route for everyvehicle before they depart.END OF THE QUESTION请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp

“