COMP4134 Algorithms and Data Structures

Project in Advanced Algorithms and Data Structures

COMP4134 UNNC

Overview

For this project, you are tasked with solving a real-world transportation problem. Formally speaking, it iscalled the pickup and delivery problem with time windows (PDPTW). The pickup and delivery problemPDP) is a type of vehicle routing problem in which customers are pairedtogether, and a pair must beserviced by the same vehicle, seehttps://developers.google.com/optimization/routing/pickup_deliveryfor example. In other words, a load must be collected from one location and delivered to anotherlocation by a single vehicle. Clearly, there are also ordering or precedence constraints to ensure that thecollection site is visited before the delivery site. If there are time windows during which the customersmust be visited, then the problem is known as the PDPTW. This problemcommonly arises in real-worldlogistics, and solution methodologies have significant practical applications.While planning the routes, there are some driver break regulations that have to be met, which includedrivers' hours rules and working time rules. To reduce complexity, we will focus on the rules highlightedin red circles, which pertain to the daily transportation problem. The objective is to decrease the totaduty time necessary for the delivery of all ordersThe two regulations are briefly introduced below; detailed information can be found in Table 1 (seehttps://assets.publishing.service.gov.uk/media/5e14b5b040f0b65dbed713a0/simplified-guidance-eu-hours-working-time-rules.pdf and Table 2). Regarding Regulation (EC) No 561/2006, the followingconstraints should be m代写COMP4134  Algorithms and Data Structures etThe maximum daily driving time is 9 hours.Driver breaks could be one of the following: (a) For every 4.5 hours of driving, drivers must take abreak of at least 45 minutes. This break starts a new 4.5-hour driving period. (b)For every 4.5hours of driving, drivers can take either one 45-minute break ortwosmallerbreaks,one of atleast 15 minutes followed by another of at least 30 minutes.Anotherregulation is Directive 2002/15/EC, which is a legislative act concerning the working time formobile workers engaged in road transport activities. It sets out the maximum limits onworking time,including driving time, other work-related activities, and on-call time. The following constraints should bemet:

Drivers cannot work more than 6 hours without a break; a break should be at least 15 minuteslong.

• Drivers need a 30-minute break if they work between 6 to 9 hours in total.2able 1 A summary of the EU drivers’ hours rules and sector specific working time rules

Table 2 Summarised daily allowed drive time, duty time and route durationDeadline and Late penaltyDeadline is 6pm Monday the 9th of December, for each day the coursework is late, a penalty of 10% willbe deducted.Plagiarism is not allowed, and your source code and documentation will be examined for similarities.Please note that this is individual work, not a group project. You are encouraged to conduct individualresearch and free to implement algorithms that have already been published, but copying others’ workis strictly forbidden. (Please consult the academic misconduct policy for further details:https://www.nottingham.ac.uk/studentservices/servicedetails/appeals-complaints-andconduct/academic-misconduct.aspx)Submission instructionsTo submit your code and report for this module, please use the provided link on the Moodle page. ouralgorithm should be implemented in Java, and your report, which is limited to 2000 words, must besubmitted in PDF format. Please refer to the “Grading Criteria” section below, which lists the requirements.The submission link will be active before the deadline. Please note that submissions sent via email will notbe accepted. For comprehensive guidelines on the submission process, please consult the “Submission”section below.SubmissionGiven that this is a Master's level project, it is designed to emphasizeindependent study and research.However, certain algorithms and data structures relevant to theproject will be introduced in the coursemodule COMP4133. Proficiency in Java isrequired for the successfulcompletion of this project.The necessary files for this assignment are available for download from Moodle. These include:

`Input.json`: An example file that you will read as input.

• `Output.txt`: A sample output file that corresponds to the `Input.json` input.

Your Java code should fulfill the following requirements:

1. Read the content of `Input.json`.
2. You are required to devise your own algorithm and apply it to solve the given problem.Implementing an existing algorithm from the literature is fine, but please cite it in your report.You may select from various algorithmic approaches, including but not limited to dynamicprogramming, linear programming, and heuristics. Your implementation will be submitted forgrading.Print the solution follow the expected ‘Output.txt’.

For instance, given the content of 'Input.json' provided: Please refer to the video recording on the module page for this module for a detailed explanation of

the JSON content. 3The expected 'Output' should look like this:

Full mark Comment Is the output correct?20% The correct answer will receive fullmarks. Marks may be deducted forthe following reasons: partiallycorrect answers with minormistakes, or correct outputaccompanied by other issues. Thiswill be tested using a new dataset,

which is not provided by themodule. For programs involvingrandomness, ensure that you useyour student ID as the seed.How is the time complexity of the program?10% Forthose who provide the correctanswer, their run time will berecorded. Those whose run timefalls into the first quantile will

receive full marks. Those in theecond quantile will receive 7.5% of

the total marks, the third quantile5%, and the last quantile 2.5%.How is the solution quality of the program?10% ease indicate the durationequired for the solution toomplee.pickup and delivery pairs)ihin run time of 30 seconds. Forhose whose solution is better thane benchmark solution, theranking will be determined by thespeed of completion; the quickerthe completion, the higher the. Participants whose

will be awarded full points. Thosein the second 25% bracket will earnWell formatted code5% Is the program well formatted(following Java namingconventions, high readablity, 6appropriate error handling, adhere

to Object-Oriented Programmingparadigm etc.)Appropriate comments5% Does the program containappropriate comments?Criteria of report 50% Well-written literature review10% In the literature review, is theliterature sufficient, up-to-date,well-organised, and does it followproper logical flow? The reportshould be confined to a maximumof 2000 words, excluding literatureand pseudo code.Evaluation of the Chosen Algorithm, Data structurend Methodology15%

Provide a clear rationale for thealgorithm selected and theapproach taken to solve theproblem.Indicate whether the algorithm isentirely of your own design or if itis an implementation of an existingalgorithm from the literature.o the project.Provide clear and effective documentation of youralgorithm10% In your report, ensure that youprovide a clear and conciseexplanation of your algorithm.Utilise clear instructions, supportedby pseudocode, diagrams, andother visual aids as necessary toenhance understanding.Evaluating solutionquality and output validationaccuracy10% Justify the solution’squality andconfirm that the given output iscorrect.Report the result clearly5% Report the results clearly, forexample, by using visuals, plots,andstatistics such as the mean andstandard deviation of a number ofruns.Additional Credit: We are primarily evaluating compliance with the rules for individual days. However, an extra 10% bonus (up tomaximum of 100%) will be awarded ifrule sets beyond those highlighted in the red squares are taken into account. Definitions Standard inputSystem.in, means that the stream from which input to the program istaken. Typically this is thekeyboard, but it can be specified that input is to come from a serial port or a disk file.Standard outputSystem.out, means that the stream to which output from the program is sent. Typically this is a display,but it can be redirected to a serial port or a file.

Submission You must submit a single Java source code file containing all your code for this coursework. This filemust be called AADS.java and must not require any other files outside of the standard Java packageswhich are always available. The file must compile and execute without warnings or errors using thecommand.Compile: javac -encoding UTF-8 -sourcepath . AADS.javaExecute: java -Dfile.encoding=UTF-8 -XX:+UseSerialGC -Xss64m -Xms1920m -Xmx1920m AADS <Input.json > Output.txtthat you read and understand allthe information below.You program MAY have multiple classes if you wish,but only in one java file. And only the class withyour main method SHOULD be marked as public.our program MUST read its input from standard input.ogram submitted will be run inside a sandbox. The sandbox will allocate 2GB of memory for yourprogram. Your entire program, including its runtime environment, must execute within this memorylimit. For Java, the runtime environment includes the interpreter (JVM).We suggest that you do not use package statements (that is, we suggest that your solution reside in the“default package”).Please use JDK versions later than 7.

Possible results A submission can have the following results:7CORRECT The submission passed all tests: you solved this problem!0% will be given to errors listed below:COMPILER-ERROR There was an error when compiling yourprogram.Note that when compilation takesmore than 30 seconds, it is aborted and this counts as a compilation error.TIMELIMIT Your program took longer than the maximum allowed time for this problem, 5 seconds.Therefore it has been aborted.This might indicate that your program hangs in a loop or that yourolution is not efficient enough.

RUN-ERROR There was an error during the execution of your program. This can have a lot of differentcauses like division by zero, incorrectly addressing memory (e.g., by indexing arrays out of bounds),

trying to use more memory than the limit, reading or writing to files, etc. Also check that your programexits with exit code 0!NO-OUTPUT Your program did not generate any output. Check that you write to standard out.

OUTPUT-LIMIT Your program generated more output than the allowed limit. The solution is consideredincorrect.

WRONG-ANSWER The output of your program was incorrect. This can happen simply because yoursolution is not correct, but remember that your output must comply exactly with the specifications ofthe judges. See testing below for more details. The judges may havepreparedmultiple test files for eachproblem.

The driver takes a break of 30 minutes after working for 6 hours. Then, the driver resumes driving foranother 30 minutes, followed by another break of 30 minutes, because of the 4.5 hours of driving timeaccumulated.Scenario 1 a

1. However, this driver break assignment can be improved by allocating a 45- minute break when theduty time has been accumulated to 6 hours rather than allocating an additional 30-minute break whenreaching 4.5 hours of driving because the driving hours have been reset by the 45-minutes break.8Scenario 1 b Scenario 2

1. This scenario is similar to the previous one, but the driver in the previous scenario completes hisjourney after 2.5 hours of driving after the first break. In this case, however, the driver continues todrive for 4 hours and 40 minutes after the first break.

Scenario 2 a

1. Allocating 45 minutes to reset the driving break is no longer a good idea in this scenario becauseanother break will be triggered due to reaching 4.5 hours driving time. As a result, the journey will take12 hours and 10 minutes.Scenario 2 b Scenario 3

2. After working for 6 hours, a break of 30 minutes is given. Then, driving is resumed for 2.5 hours moreand another break of 15 minutes is taken, as the duty time has reached 9 hours. After one more hour ofdriving, another break of 30 minutes is required, because the total driving time is 4.5 hours.910

Scenario 3 a

1. This driver breaks assignment can be improved by allocating a 45-minute break when the duty timereaches 6 hours. This journey requires no additional breaks because the 45-minute break reset thedriving hours.

Scenario 3 b Scenario 4

1. This scenario is similar to the previous one, except that in the previous scenario, the driver completesthe journey after 2.5 hours of driving after the first break. However, after the first break, the drivercontinues to drive for 4 hours and 40 minutes.Scenario 4 a11

1. Allocating 45 minutes to reset the driving break is no longer a good idea in this scenario becausanother break will be triggered due to reaching 4.5 hours driving time. As a result, the journey will take12 hours and 10 minutes.Scenario 4 b

1. However, if we increase the second break in Scenario 4 a from 15 to 30 minutes, no further driverbreaks are required. As a result, the journey is reduced to 11 hours and 40 minutes.

Scenario 4 c Scenario 5

The arrival time at the customer site was 2:30, but a wait of 15 minutes was required due to the timewindow constraint. A break was assigned during the wait. A duty break of 15 minutes was given afterworking for 6 hours. After that, driving was resumed for 45 minutes, when a driving break was neededbecause the total driving time was 4.5 hours.

Scenario 5 a12

1. This driver breaks assignment can be improved by allocating a 30-minute break after 6 hours of duty.Because the accumulated 45 minutes break reset the driving hours, this journey requires no additionalbreaks.

Scenario 5 b Scenario 6

1. This scenario is similar to the previous one. But in this case, the driver continues to drive for 4 hourand 40 minutes after the second break.Scenario 6 a

1. Allocating 30 minutes break instead of 15 mintues to reset the driving break is no longer a good ideain this scenario because another break will be triggered due to reaching 4.5 hours driving time. As aresult, the journey will take 11 hours and 55 minutes.Scenario 6 bA summary of the scenar