代写program、代做c/c++，Java程序

日期：2023-10-29 10:52

Assignment Description

Abstract: Traveling Salesman Problem (TSP) is a classical combinatorial problem that is

deceptively simple. This problem is about a salesman who wantsto visit n customers cyclically.

In one tour, the salesman must visit each customer just once and should finish up where he

started. Since each customer is situated in different locations, the distance between every

customer will be different. The objective is to find the shortest round-trip route that visits

each customer once and then returns to the starting customer. The dataset with 100

customers is provided in the zip file (‘TSPTW_dataset.txt’).

In this assignment, students are required to finish the following five tasks:

(1) Classical TSP

A genetic algorithm is used to find the shortest round-trip route of these 100 customers. The

locations of customers are given in TSPTW_dataset.txt. Students should visualize the roundtrip route and provide the total distance.

(2) Dynamic optimization problem

In the real-world TSP, the location and number of customers may vary with time, such a TSP

problem can be considered a dynamic optimization problem. Considering such a scenario:

For each environment ! = 0, … ,5, the first 50 + 10! customers are allowed to be visited.

Besides, the location of a customer varies with the environment !,

)!"# = ) + 2! ? cos /

0

2 !1,

2!"# = 2 + 2! ? sin /

0

2 !1,

where )!"# and 2!"# are the new X coordinate and Y coordinate at environment ! ,

respectively. ) and 2 are the X coordinate and Y coordinate provided in the

TSPTW_dataset.txt. Assuming that the environmental variable ! is changed every 100

generations, students should try to design a genetic algorithm to track the shortest roundtrip route for each environment ! by reusing the solutions from the last environment to

accelerate the search in the new environment and then compare the results from the genetic

algorithm without reusing the solutions from the last environment.

(3) Large-scale optimization problem

By adding 100 to the X coordinate for each customer in the TSPTW_dataset.txt, additional

100 customers can be formed. Regarding the newly formed 100 customers and the original

100 customers as a whole, the new problem can be regarded as a large-scale problem. For

this large-scale problem, the customers can be divided into several small-scale regions by

using clustering techniques, e.g., K-means. The salesman must finish visiting all the customers

within the region before visiting any other customers in other regions. In this task, students

are required to combine the clustering technique with a genetic algorithm to handle the largescale optimization problem.

(4) Multi-objective optimization problem

The salesman may consider more than one objective. For example, the salesman not only

wants to minimize the travel distance of the round-trip route but also maximize the sales

profit. Assume that the sales profit of each customer can be randomly generated between

[1,50], the two objective functions, (i.e., total travel distance 5$ and total sales profit 5%) may

be conflicting, that is, a solution cannot satisfy the maximal sales profit and minimal travel

distance at the same time. The multi-objective optimization problem can be formulated as

< min 5$ , max 5% >. An alternative approach is to change the multi-objective optimization

problem to a single-objective optimization problem by weighting the two objective functions,

min (5$ ? ?5%),

where ? (? > 0) is the weight on 5%. Students can specify the ? value to get the optimal

solution.

In addition to the weighting objective functions-based method, students should develop a

Pareto dominance selection-based evolutionary algorithm to handle the multi-objective

optimization problem and discuss the advantages and disadvantages of the weighting

objective functions-based method and Pareto dominance selection-based method.

(5) Time window constraint problem

The salesman is required to visit a certain customer within a certain time window, i.e., the

salesman should visit the customer between “READY TIME” and “DUE TIME”, and the time

window for each customer is given in TSPTW_dataset.txt. The travel time between customers

is computed by the Euclidean distance between customers. Considering the time window as

an additional objective, students are required to develop a Pareto dominance selection-based

evolutionary algorithm to solve the problem by optimizing the following three objectives:

minimize total travel distance, maximize total sales profit, and minimize the total violation

value of the time window, where the total violation value of the time window is the

summation of the violation value of the time window for each customer. For example, “READY

TIME” and “DUE TIME” of the “CUST NO 3” are 2 and 61, respectively. If the salesman visits

the “CUST NO 3” at time 63, the violation value of the time window is 63-61=2. If the salesman

visits the “CUST NO 3” at time 1, the violation value of the time window is 2-1=1.

Discussion and analysis:

Students must give the details of the designed algorithms and perform sensitive studies for

the above tasks with the various parameters, for example, the crossover and mutation rates,

the population size, and the number of generations, and discuss the effects of changing these

parameters. Students need to show their results in various formats, such as tables, figures,

etc.