[SOLVED] COMP4134 Project in Advanced Algorithms and Data Structures Java

Project in Advanced Algorithms and Data Structures

COMP4134

Overview

For this project, you are tasked with solving a real-world transportation problem. Formally speaking, it is called the pickup and delivery problem with time windows (PDPTW). The pickup and delivery problem (PDP) is a type of vehicle routing problem in which customers are paired together, and a pair must be serviced by the same vehicle, seehttps://developers.google.com/optimization/routing/pickup_delivery for example. In other words,a load must be collected from one location and delivered to another location by a single vehicle. Clearly, there are also ordering or precedence constraints to ensure that the collection site is visited before the delivery site. If there are time windows during which the customers must be visited, then the problem is known as the PDPTW. This problem commonly arises in real-world logistics, and solution methodologies have significant practical applications.

While planning the routes, there are some driver break regulations that have to be met, which include drivers’ hours rules and working time rules. To reduce complexity, we will focus on the rules highlighted in red circles, which pertain to the daily transportation problem. The objective is to decrease the total duty time necessary for the delivery of all orders.

The two regulations are briefly introduced below; detailed information can be found in Table 1 (see

https://assets.publishing.service.gov.uk/media/5e14b5b040f0b65dbed713a0/simplified-guidance-eu-drivers-hours-working-time-rules.pdfand Table 2). Regarding Regulation (EC) No 561/2006, the following constraints should be met:

•    The 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 a break of at least 45 minutes. This break starts a new 4.5-hour driving period. (b) For every 4.5 hours of driving, drivers can take either one 45-minute break or two smaller breaks, one of at least 15 minutes followed by another of at least 30 minutes.

Another regulation is Directive 2002/15/EC, which is a legislative act concerning the working time for mobile workers engaged in road transport activities. It sets out the maximum limits on working time, including driving time, other work-related activities, and on-call time. The following constraints should be met:

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

•    Drivers need a 30-minute break if they work between 6 to 9 hours in total.

Table 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 duration

Deadline and Late penalty

Deadline is 6pm Monday the 9th of December, for each day the coursework is late, a penalty of 10% will be 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 individual research and free to implement algorithms that have already been published, but copying others’ work is strictly forbidden. (Please consult the academic misconduct policy for further details:

https://www.nottingham.ac.uk/studentservices/servicedetails/appeals-complaints-and- conduct/academic-misconduct.aspx)

Submission instructions

To submit your code and report for this module, please use the provided link on the Moodle page. Your  algorithm should be implemented in Java, and your report, which is  limited to 2000 words, must be  submitted 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 not  be accepted. For comprehensive guidelines on the submission process, please consult the “Submission” section below.

Submission

Given that this is a Master’s level project, it is designed to emphasize independent study and research.   However, certain algorithms and data structures relevant to the project will be introduced in the course module COMP4133. Proficiency in Java is required for the successful completion 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 dynamic

programming, linear programming, and heuristics. Your implementation will be submitted for grading.

3.    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.

The expected ‘Output‘should look like this:

Which appears as follows in the text file:

VehicleName,JobId,JourneyTime,ArrivalTime,WaitTime,DelayTime,ServiceTime,DepartureTime,Break1Ti me,Break1Duration,Break2Time,Break2Duration

1,Vehicle 1 start,0h0m,08:00,0h0m,0h0m,0h0m,8h0m,,,, 1,C-0,0h0m,08:00,0h0m,0h0m,0h0m,8h0m,,,,

1,C-1,4h0m,12:00,0h0m,0h0m,0h0m,12h0m,,,,

1,D-0,0h0m,12:00,0h0m,0h0m,2h0m,14h0m,14:00,0h15m,14:45,0h30m 1,D-1,2h0m,16:45,0h0m,0h0m,0h0m,16h45m,,,,

1,Vehicle 1 end,0h30m,17:15,0h0m,0h0m,0h0m,17h15m,,,,

Grading Criteria