遗传算法C++实现求解VRP问题_vrp遗传算法编码

 车辆路径问题（Vehicle Routing Problem, VRP）

1.问题描述

车辆路线问题（VRP）：一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目 标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。

2.VRP基因编码和解码方法 

假设1：仅有1个配送中心，在某一时刻，所有负责配送的车同时从 配送中心出发，分别完成各自的配送任务后，再回到配送中心（送奶路线）；

假设2：配送中心有若干辆车(如6辆)，一辆车可负责一个或多个点的配送任 务，且每个配送点只被服务一次。

假设3：每辆车有一定的载重量（如90t）和里程限制（如 200km），车的载重和行驶里程不可超过指定的值。

假设4：车辆必须在客户允许的时间窗处进行配送服务，此处采用硬时间窗

·编码

对于此问题，采用自然数编码，每个自然数代表一个客户，0代表配送中心，例如：

·解码

在解码过程中应该使每辆车在满足各种约束条件下为尽可能多的客 户提供服务。首先，安排第一辆车从配送中心0出发，到序列中的第一 个客户2处为其提供服务，服务完后再综合考虑车辆容量限制、行驶总路程限制以及序列中第二个客户5的时间窗限制等条件，决定是否直接到客户5处提供服务。 假若条件允许，则到客户5处，服务完再分析是否直接到客户8处提 供服务，依次类推；假若不能为客户8提供服务，则该辆车直接由客户5处返回配送中心，形成一个配送回路0->2->5->0。

接下来，安排第二辆车从配送中心0出发，直接到客户8处，服务完 再分析是否到后续客户3处为其服务。

依此类推，直到所有的客户都被服务为止，将客户序列拆分成了若 干个满足约束条件的配送回路，对应一个可行解。

注：为了使任何一个个体解码后都能对应可行解，本节假设从配送中心派一辆车单独为某一个客户提供服务，都可以在该客户的第一个时间窗内到达并完成服务。在实际中，假若从配送中心出发的车辆直接到 某个客户处服务，不能在该客户的第一个时间窗内完成服务，则说明该客户的第一个时间窗不可用，可以删掉该时间窗。因此，这种假设是有 意义的。

本程序可以调节是否可用交叉和变异，及其参数值，以及锦标赛法选取的后代数目可在参数设置区进行调节(默认0.1倍种群大小) ,仅仅将下面的两个数据文件与GA.cpp文件放在一个工程目录下即可运行代码。

3.实例：

设有一配送中心为10个客户提供货物配送服务，序号0表示配送中心， 序号1，2，…，10表示10个需求点。

配送中心共有6辆同型号的车辆，每辆车的最大装载量均为90t，每辆车的最长行驶距离均200km；

动用每辆车的固定成本均为50元，每辆车行驶每公里成本为20元；

配送中心及各个需求点之间的距离见表1；

车辆在配送中心及各个需求点之间的行驶时间见表2；

各个需求点的需求量、服务时间及可利用的时间窗见表3；

为了使总配送成本达到最少，需要安排多少辆车完成配送任务?每辆车的配送路径是什么?

 

 

 4.算法设计

（1）选择算子：随机遍历抽样（Stochastic universal sampling，SUS）

随机遍历抽样是轮盘选择的修改版本。使用相同的轮盘，比例相同，但使用多个选择点，只旋转一次转盘就可以同时选择所有个体。 这种选择方法可以防止个体被过分反复选择，从而避免了具有特别高适应度的个体垄断下一代。因此，它为较低适应度的个体提供了被选择的机会， 从而减少了原始轮盘选择方法的不公平性。

 （2）交叉算子：2点交叉（2-point crossover）+ 交叉映射+交叉概率

在2点交叉中， 交换两个父代个体中交叉点之间的基因序列，并形成交叉映射关系， 再按照交叉映射关系对其他位点的基因进行变换，得到两个新个体。

上面的两个父代对于选定的交叉点可以形成如下交叉映射关系：

4—5、8—7、2—10、11—3。

按照这样的映射关系，交叉后得到两个新个体

 

 （3）变异算子：交换突变（Swap mutation）+变异概率

（4）终止规则

采用一定的进化代数N作为终止规则，即当进化代数达到N时，终止计算，并把历代种群个出现的适应度最大的个体作为问题的最优解输出。

5.算法实现

（1）语言：C++

（2）环境：

操作系统：windows10家庭版

IDE：Visual Studio 2022

CPU：Intel Core i7-10875H 2.3GHz   实际速度：约4.3Ghz

内存：16GB DDR4 2933MHz

（3）源代码

//Time.h
 
#pragma once
#include<stdexcept>
 
// 时间窗类
class Time
{
public:
	// 默认构造函数
	Time() :start{ 0 }, end{ 24 } {}
	Time(unsigned start_, unsigned end_) :start{ start_ }, end{ end_ } {}
	//运算符重载
	bool operator<=>(const Time& other_time_window)const = delete;
	bool operator==(const Time& other_time_window)const = default;
	const auto& operator[](size_t index)const 
	{
		if (index == 0)return start;
		if (index == 1)return end;
		throw std::out_of_range{ " Time 对象下标越界!" };
	}
	unsigned start;		// 起始时刻
	unsigned end;		// 结束时刻
};

// Customer.h
#pragma once
#include<array>
#include<vector>
#include<compare>
 
#include"Time.h"
 
const size_t Window_num{ 2 };	// 时间窗个数
// 客户类，包括配送中心
class Customer
{
public:
	// 默认构造函数
	Customer();
	// 主构造函数
	Customer(unsigned number, unsigned requirement, double service_time, std::array<Time, Window_num> time_window);
	// 删除副本成员
	Customer(const Customer&) = delete;
	Customer& operator=(const Customer&) = delete;
	// 默认移动成员
	Customer(Customer&&)noexcept = default;
	Customer& operator=(Customer&&)noexcept = default;
	//运算符重载
	bool operator==(const Customer& other_customer) const { return m_number == other_customer.get_number(); }
	const auto& operator[](size_t index)const { return m_time_window.at(index); }
	auto& operator[](size_t index) { return const_cast<Time&>(std::as_const(*this)[index]); }
	// 类型转换
	operator size_t()const { return m_number; }
 
 
	// 访问器 //
 
	const unsigned get_number() const { return m_number; }
	const unsigned get_requirement() const { return m_requirement; }
	const double get_service_time() const { return m_service_time; }
	// 展示顾客属性
	void show_customer() const;
	// 获得与另一个顾客的距离
	unsigned get_distance(const size_t other_customer_number)const;
	unsigned get_distance(const Customer& other_customer)const;
	unsigned get_distance(const Customer* other_customer)const;
	// 判断是否在时间窗内
	double is_in_window(double time)const;
 
	// 访问器 //
 
	// 无更改器 //
 
	// 展示固有参数
	static void show_parameters();
 
	static const Customer Distribution_Center;							// 配送中心
	inline static std::vector<std::vector<int> > Distance_Matrix{};		// 客户以及配送中心之间的距离矩阵
	inline static std::vector<Customer> Customer_Array{};				// 客户序列，一般只在初始化时添加，不可修改
	inline static int Size{};											// 配送中心+客户数
	
 
private:
	unsigned m_number;											// 序号
	unsigned m_requirement;										// 需求量，单位t
	double m_service_time;										// 服务用时
	std::array<Time, Window_num> m_time_window{};				// 时间窗
};

// Car.h
#pragma once
 
#include"Customer.h"
 
// 车辆类
class Car
{
public:
	// 主构造函数
	explicit Car(unsigned number) :m_number{ number } {}
	// 默认副本成员
	Car(const Car&) = default;
	Car& operator=(const Car&) = default;
	// 默认移动成员
	Car(Car&&)noexcept = default;
	Car& operator=(Car&&)noexcept = default;
	//运算符重载
	const Customer* operator[](int index)const;
	Customer* operator[](int index) { return const_cast<Customer*>(std::as_const(*this)[index]); }
	// 类型转换
	operator size_t()const { return m_number; }
 
	// 访问器 //
 
	unsigned get_cost()const { return m_cost; }
	// 展示车辆属性
	void show_car()const;
 
	// 访问器 //
 
 
	// 更改器 //
 
	// 在路线后添加一个客户
	bool add_customer(const Customer* customer);
	//void add_customer(const Customer& customer);
	// 在时刻表后添加对应的时刻
	//void add_time(double time) { m_time.push_back(time); }
	// 计算配送成本
	void calculate_cost();
	// 更新时刻表
	bool update_time_list();
 
	// 更改器 //
 
	// 展示固有参数
	static void show_parameters(int choice = 0);
	
	inline static  unsigned Max_Amount{ 6 };					// 车辆最大数量
	inline static  unsigned Max_Load{ 90 };						// 车辆载重量，单位t
	inline static  unsigned Max_Distance{ 200 };				// 车辆最大行驶距离，单位km
	inline static  unsigned Fixed_Cost{ 50 };					// 车辆固定成本
	inline static  unsigned Variable_Cost{ 20 };				// 车辆单位距离行驶成本
	inline static  std::vector<std::vector<double> > Time_Matrix{};		// 汽车配送时间矩阵
 
private:
	unsigned m_number;						// 车辆汽车序号
	unsigned m_load{};						// 车辆车实际载重量
	unsigned m_distance_traveled{};			// 车辆车实际行驶距离
	std::vector<const Customer*> m_route{};	// 车辆车所经过的路径数组，包括出发和返回配送中心
	std::vector<double> m_time{};			// 车辆车到达时刻，与路径数组大小相同
	int m_customer_number{};				// 车辆车路径经过的客户数
	unsigned m_cost{};						// 车辆车成本，包括变动和固定成本
};

//Individual.h
#pragma once
 
#include"Car.h"
// 个体类
class Individual
{
public:
	// 默认构造函数
	Individual() :m_DNA{}, m_fitness{}, m_genetic_probability{}, m_sum_probability{}, m_cost{ 999999 }, m_number_of_violations{ 999999 } {}
	// 主构造函数
	Individual(const std::vector<int>& dna, unsigned cost = 0, std::vector<Car> car_array = std::vector<Car>{}, unsigned number_of_violations = 0);
	// 运算符重载
	const int& operator[](size_t index)const { return m_DNA.at(index); }
	int& operator[](size_t index) { return const_cast<int&>(std::as_const(*this)[index]); }
 
	// 访问器 //
 
	const auto& get_DNA()const { return m_DNA; }
	const unsigned get_cost()const { return m_cost; }
	const double get_fitness()const { return m_fitness; }
	const double get_genetic_probability()const { return m_genetic_probability; }
	const double get_sum_probability()const { return m_sum_probability; }
	const unsigned get_number_of_violations()const { return m_number_of_violations; }
 
	// 访问器 //
 
 
	// 更改器 //
 
	auto& set_DNA() { return m_DNA; }
	void update_fitness() { m_fitness = 1.0/m_cost; }
	void multiply_fitness(double value, unsigned times) { m_fitness *= pow(value, times); }
	void set_genetic_probability(double probability) { m_genetic_probability = probability; }
	void set_sum_probability(double sum_probability) { m_sum_probability = sum_probability; }
 
	// 解码
	void decode();
	// 更新并展示解
	void Update_and_display_solutions();
	// 计算成本
	unsigned update_cost();
	// 展示个体
	void show_individual()const;
 
	// 更改器 //
 
	static std::vector<Individual> Best_Individuals;		// 最优个体,包括多个 
 
private:
 
	std::vector<int> m_DNA;					// 基因序列
	double m_fitness;						// 适应度,为成本的倒数
	double m_genetic_probability;			// 遗传概率
	double m_sum_probability;				// 轮盘赌累加值,左闭右开区间时，该个体成功遗传子代
 
	// 性状 //
	unsigned m_cost;						// 成本
	std::vector<Car> m_car_array{};			// 电动车序列
	unsigned m_number_of_violations;		// 违法约束次数
	// 性状 //
};

// Genetic_Algorithm.h
#pragma once
 
#include<string>
 
#include"Individual.h"
 
 
// 遗传算法类
class Genetic_Algorithm
{
public:
	// 默认构造函数
	Genetic_Algorithm() = default;
	// 删除副本成员
	Genetic_Algorithm(const Genetic_Algorithm&) = delete;
	Genetic_Algorithm& operator=(const Genetic_Algorithm&) = delete;
	// 默认移动成员
	Genetic_Algorithm(Genetic_Algorithm&&)noexcept = default;
	Genetic_Algorithm& operator=(Genetic_Algorithm&&)noexcept = default;
 
	
	// 初始化种群
	void initialize();
 
	// 获得适应度
	void get_fitness();
	// 获得遗传概率
	void get_genetic_probability();
	// 获得轮盘赌累加概率
	void get_sum_probability();
 
	// 遗传算子 //
 
	// 选择算子，轮盘赌多选法
	void selection();
	// 交叉算子，两点交叉+映射法
	void crossover();
	// 变异算子，两点交换变异
	void mutation();
 
	// 遗传算子 //
 
	// 遗传算法入口
	void genetic_algorithm();
 
	// 展示固有参数
	static void show_parameters(int choice = 0);
 
 
 
	inline static  size_t Po_Size{ 512 };					// 种群规模，一般为20~300
	inline static  size_t Iterations{ 512 };				// 进化代数，一般为100~500
	inline static double Crossover_P{ 0.5 };				// 交叉概率，一般为0.4~0.99
	inline static double Mutation_P{ 1.0/1024 };			// 变异概率，一般为0.001~0.2
	inline static const double Punish{ 0.125 };				// 惩罚系数
	static Individual Best_Individual_in_History;			// 历史最优个体
 
private:
	std::vector<Individual> m_population{};					// 种群
 
 
};

//UI_Manage.h
#pragma once
 
#include"Genetic_Algorithm.h"
 
class UI_Manage
{
public:
	// 展示菜单 
	void Show_Menu()const;
	// 退出程序0
	void exit_system()const { exit(0); }
 
	// 读取文件1
	bool read_file(std::string_view distance_file = "节点距离.txt", std::string_view time_file = "行驶时间.txt", std::string_view customer_file = "客户需求和服务时间.txt");
 
	// 展示所有参数2
	void show_all_parameters()const;
 
	// 展示文件路径3
	void show_file_path()const;
 
	// 开始求解4
	void start_solve(std::string_view distance_file = "节点距离.txt", std::string_view time_file = "行驶时间.txt", std::string_view customer_file = "客户需求和服务时间.txt");
 
	// 修改参数5
	void modify_parameters();
 
private:
 
	bool m_file_read{ false };  
};

//Customer.cpp
#include "Customer.h"
 
#include<iostream>
#include<format>
 
using
std::array,
std::cout, std::endl,
std::format;
 
const Customer Customer::Distribution_Center{};
 
// 默认构造函数
Customer::Customer() :m_number{}, m_requirement{}, m_service_time{}, m_time_window{} {}
// 主构造函数
Customer::Customer(unsigned number, unsigned requirement, double service_time, std::array<Time, Window_num> time_window)
	:m_number{number},
	m_requirement{ requirement },
	m_service_time{ service_time },
	m_time_window {time_window}
{}
 
// 访问器 //
 
// 判断是否在时间窗内，不在，则返回负数
double Customer::is_in_window(double time)const
{
	if (time < (*this)[0][0])
	{
		// 在第一个窗口前
		return time - (*this)[0][0];
	}
	else if (time <= (*this)[0][1])
	{
		// 在第一个窗口
		return 0;
	}
	else if (time < (*this)[1][0])
	{
		// 在两窗口中
		return time - (*this)[1][0];
	}
	else if (time <= (*this)[1][1])
	{
		// 在第二个窗口
		return 0;
	}
	else
	{
		// 在第二个窗口后,不能调整
		return 1;
	}
}
// 展示顾客属性
void Customer::show_customer() const
{
	cout << format("|{:4}|{:4}|{:.2f}|{:>2}{:<2},{:>2}{:<2}|{:>2}{:<2},{:>2}{:<2}|",
		m_number, m_requirement, m_service_time,
		"[", m_time_window[0].start, m_time_window[0].end, "]",
		"[", m_time_window[1].start, m_time_window[1].end, "]");
}
// 获得与另一个顾客的距离
unsigned Customer::get_distance(const size_t other_customer_number)const
{
	return Distance_Matrix[this->m_number][other_customer_number];
}
unsigned Customer::get_distance(const Customer& other_customer)const
{
	return this->get_distance(static_cast<size_t>(other_customer.m_number));
}
unsigned Customer::get_distance(const Customer* other_customer)const
{
	return this->get_distance(static_cast<size_t>(other_customer->m_number));
}
 
// 访问器 //
 
void Customer::show_parameters()
{
	using std::vector;
	cout << format("{}{}\n", "配送中心 + 客户数:", Size);
	cout << format("{:^30}\n", "节点距离矩阵");
	if (Distance_Matrix.empty())
	{
		cout << "距离矩阵为空!\n";
	}
	else
	{
		for (const auto& row : Distance_Matrix)
		{
			for (const auto& distance : row)
			{
				cout << format("{:2} ", distance);
			}
			cout << endl;
		}
	}
	cout << format("{:^30}\n", "客户序列");
	if (Distance_Matrix.empty())
	{
		cout << "客户序列为空!\n";
	}
	else
	{
		for (const auto& customer : Customer_Array)
		{
			customer.show_customer();
			cout << endl;
		}
	}
	
}

// Car.cpp
#include "Car.h"
 
#include<iostream>
#include<format>
 
using
std::cout,std::endl,
std::format,
std::vector;
 
// 运算符重载
const Customer* Car::operator[](int index)const
{
	if (index >= 0)return m_route.at(index);
	else return m_route.at(0);
}
 
// 访问器 //
 
// 展示车辆属性
void Car::show_car()const
{
 
	if (m_route.empty())
	{
		cout << format("车辆{}未发车!", m_number);
		return;
	}
	cout << format("{:6}{:2}{:6}:{:^7}", "车辆", m_number, "路线", 0);
	for (const Customer* customer : m_route)
	{
		cout << format("{:<4}{:<3}", "->", customer->get_number());
	}
	cout << "->  0  " << endl;
 
	double start_time{ m_time[0] - Time_Matrix[0][*m_route[0]] };
	double end_time{ m_time.back() + Time_Matrix[*m_route.back()][0] + m_route.back()->get_service_time() };
	cout << format("{:6}{:2}{:6}:{:^9.2f}", "车辆", m_number, "时刻表", start_time);
	for (const auto& time : m_time)
	{
		cout << format("{:^7.2f}", time);
	}
 
	cout << format("{:^7.2f}\n", end_time);
 
	cout << "成本:" << m_cost << endl;
	cout << "载重:" << m_load << endl;
	cout << "行程:" << m_distance_traveled << endl;
}
 
// 访问器 //
 
// 更改器 //
 
 
// 在路线后添加一个客户
bool Car::add_customer(const Customer* customer) 
{
	m_route.push_back(customer); 
	++m_customer_number;
	unsigned load{ m_load };
	load += customer->get_requirement();
	if (load > Max_Load)
	{
		// 超重
		m_route.pop_back();
		--m_customer_number;
		return false;
	}
	unsigned distance_traveled{ m_distance_traveled };
	if (m_customer_number < 2)
	{
		distance_traveled += 2 * customer->get_distance(Customer::Distribution_Center);
	}
	else
	{
		distance_traveled -= (*this)[m_customer_number - 2]->get_distance(Customer::Distribution_Center);
		distance_traveled += customer->get_distance((*this)[m_customer_number - 2]);
		distance_traveled += customer->get_distance(Customer::Distribution_Center);
	}
	
	if (distance_traveled > Max_Distance)
	{
		// 超过路程限制
		m_route.pop_back();
		--m_customer_number;
		return false;
	}
	if (!update_time_list())
	{
		// 不符合时间窗限制
		m_route.pop_back();
		--m_customer_number;
		return false;
	}
	// 都满足限制,成功添加一个新客户
	m_load = load;
	m_distance_traveled = distance_traveled;
	return true;
}
// 计算配送成本
void Car::calculate_cost()
{
	unsigned variable_cost{};
	variable_cost += Variable_Cost * (*this)[0]->get_distance(Customer::Distribution_Center);
	for (int i{}; i < m_route.size() - 1; ++i)
	{
		variable_cost += Variable_Cost * (*this)[i]->get_distance((*this)[i + 1]);
	}
	variable_cost += Variable_Cost * m_route.back()->get_distance(Customer::Distribution_Center);
	m_cost = Fixed_Cost + variable_cost;
}
// 更新时刻表
bool Car::update_time_list()
{
 
	size_t right_customer_number{ *m_route.back() };
	if (m_customer_number < 2)
	{
		m_time.push_back(Time_Matrix[0][right_customer_number]);
		return true;
	}
	else
	{
		size_t left_customer_number{ *m_route[m_customer_number - 2ull] };
		vector<double> time_array{ m_time };	// 创建一个副本
		double new_time{ time_array[m_customer_number - 2ull] };
		new_time += m_route[m_customer_number - 2ull]->get_service_time() + Time_Matrix[left_customer_number][right_customer_number];
		time_array.push_back(new_time);
		// 检查所有客户的时间窗是否全部满足
		for (int index{}; index < m_customer_number; ++index)
		{
			double time{ time_array[index] };
			double time_difference{ m_route[index]->is_in_window(time) };
			if (time_difference == 1)
			{
				// 无法调整时刻表,时刻表原封不动
				return false;
			}
			else if (time_difference < 0)
			{
				// 尝试调整时刻表
				for (auto& time : time_array)
				{
					time -= time_difference;
				}
				index = -1;
			}
			else
			{
				// 符合此客户的时间约束
				continue;
			}
		}
		// 确定满足条件后，将修改后的副本移动到汽车时刻表中
		m_time = move(time_array);
		return true;
	}
}
 
 
// 更改器 //
 
//展示固有参数,参数为0时，输出矩阵
void Car::show_parameters(int choice)
{	
	if (choice == 0)
	{
		cout << format("{:26}{:<4}\n{:26}{:<4}\n{:26}{:<4}\n{:26}{:<4}\n{:26}{:<4}\n",
			"车辆最大数量:", Max_Amount,
			"车辆载重量,单位t:", Max_Load,
			"车辆最大行驶距离,单位km:", Max_Distance,
			"车辆固定成本:", Fixed_Cost,
			"车辆单位距离行驶成本:", Variable_Cost);
		cout << format("{:^50}\n", "汽车配送时间矩阵");
		if (Time_Matrix.empty())
		{
			cout << "汽车配送时间矩阵为空!\n";
		}
		else
		{
			for (const auto& row : Time_Matrix)
			{
				for (const auto& time : row)
				{
					cout << format("{:.2f} ", time);
				}
				cout << "\n\n";
			}
		}
	}
	else if (choice == 1)
	{
		cout << format("{:26}{:<4}\n{:26}{:<4}\n{:26}{:<4}\n{:26}{:<4}\n{:26}{:<4}\n",
			"1.车辆最大数量:", Max_Amount,
			"2.车辆载重量,单位t:", Max_Load,
			"3.车辆最大行驶距离,单位km:", Max_Distance,
			"4.车辆固定成本:", Fixed_Cost,
			"5.车辆单位距离行驶成本:", Variable_Cost);
	}
}

// Individual.cpp
#include "Individual.h"
 
#include<iostream>
#include<format>
 
//#define DEBUG
using
std::vector,
std::move,
std::cout, std::endl,
std::format;
 
// 静态成员
 
vector<Individual> Individual::Best_Individuals{ Individual{} };
 
// 主构造函数
Individual::Individual(const vector<int>& dna, unsigned cost, vector<Car> car_array ,unsigned number_of_violations)
	:m_DNA{ dna }, m_fitness{}, m_genetic_probability{}, m_sum_probability{},
	m_cost{ cost }, m_car_array{ car_array } ,m_number_of_violations{ number_of_violations }
{}
// 更改器 //
 
 
// 解码
void Individual::decode()
{
	// dna序列转化为客户序列dna_to_customer
	vector<const Customer*> dna_to_customer{};
	for (int gen : m_DNA)
	{
		for (const Customer& customer : Customer::Customer_Array)
		{
			if (static_cast<int>(customer) == gen)
			{
				dna_to_customer.push_back(&customer);
				break;
			}
		}
	}
	// 重置性状为空
	m_car_array.clear();
	m_cost = 0;
	m_number_of_violations = 0;
	// 所有客户添加到汽车序列中
	Car car = Car{ static_cast<unsigned>(m_car_array.size() + 1) };
	for (const auto* customer : dna_to_customer)
	{
		if (car.add_customer(customer))
		{
			// 添加成功,继续添加
			continue;
		}
		else
		{
			// 添加失败,调用新车
			m_car_array.push_back(move(car));
			car = Car{ static_cast<unsigned>(m_car_array.size() + 1) };
			car.add_customer(customer);
			if (m_car_array.size() <= Car::Max_Amount)
			{
				// 调用一辆车后，符合车辆数目约束
				continue;
			}
			else
			{
				// 汽车已用完，施加惩罚,每多调用一辆新车，多一次惩罚
				++m_number_of_violations;
			}
		}
	}
	m_car_array.push_back(move(car));
}
 
// 更新并展示最优解
void Individual::Update_and_display_solutions()
{
	update_cost();
	// 更新最优解
	if (m_number_of_violations == Best_Individuals.front().m_number_of_violations)
	{
		if (m_cost < Best_Individuals.front().m_cost)
		{
			// 找到更优解
			Best_Individuals.clear();
			Best_Individuals.push_back(*this);
			Best_Individuals.back().decode();
			Best_Individuals.back().update_cost();
			cout << format("{}\n", "找到更优解:");
			show_individual();
			cout << endl;
		}
		else if (m_cost == Best_Individuals.front().m_cost)
		{
			// 找到另一目标值相同的解
			bool flag{false};
			for (const auto& best_individual : Best_Individuals)
			{
				if (m_DNA == best_individual.get_DNA())
				{
					flag = true;
					break;
				}
			}
			if (!flag)// flag为0，说明这个解和已找到的最优解都不同
			{
				Best_Individuals.push_back(*this);
				Best_Individuals.back().decode();
				Best_Individuals.back().update_cost();
				cout << format("{}\n", "找到另一更优解:");
				show_individual();
				cout << endl;
			}
		}
	}
	else if (m_number_of_violations < Best_Individuals.front().m_number_of_violations)
	{
		// 找到更优解
		Best_Individuals.clear();
		Best_Individuals.push_back(*this);
		Best_Individuals.back().decode();
		Best_Individuals.back().update_cost();
		cout << format("{}\n", "找到更优解:");
		show_individual();
		cout << endl;
	}
}
// 计算成本
unsigned Individual::update_cost()
{
	for (Car& car : m_car_array)
	{
		car.calculate_cost();
		m_cost += car.get_cost();
 
	}
	return m_cost;
}
// 展示个体
void Individual::show_individual()const
{
	cout << format("\n{:-^80}\n{:*^80}\n", "", "");
	for (const Car& car : m_car_array)
	{
		car.show_car();
		cout << endl;
	}
	cout << format("{}:{}\n", "总成本", m_cost);
	if (m_number_of_violations > 0)
	{
		// 违反了约束
		cout << format("{}:{}\n", "违反约束次数", m_number_of_violations);
	}
	else
	{
		cout << format("{}\n{:*^80}\n{:-^80}\n", "符合约束", "", "");
	}
}
 
// 更改器 //

// Genetic_Algorithm.cpp
#include "Genetic_Algorithm.h"
 
#include<format>
#include<iostream>
#include<random>
#include<functional>
 
//#define DEBUG
using
std::vector, std::array,
std::format,
std::cout, std::endl,
std::move;
 
Individual Genetic_Algorithm::Best_Individual_in_History{ vector<int>{1, 6, 10, 5, 2, 9, 7, 8, 4, 3} };
 
// 类外函数 //
 
// 生成伪随机正整数，左闭右闭区间
unsigned Pseudo_random_number(unsigned min, unsigned max)
{
	using std::random_device, std::default_random_engine, std::uniform_int_distribution;
	random_device seeder;										// 真随机数作为种子
	default_random_engine generator{ seeder() };				// 伪随机数生成器
	uniform_int_distribution<unsigned> distribution{ min,max };	// 整数均匀分布	
	return distribution(generator);
}
// 伪随机数生成器PRNG，正整数类，左闭右闭区间
auto create_pseudo_random_number_generator(unsigned min, unsigned max)
{
	using std::random_device, std::default_random_engine, std::uniform_int_distribution, std::bind;
	random_device seeder;										// 真随机数作为种子
	default_random_engine generator{ seeder() };				// 伪随机数生成器
	uniform_int_distribution<unsigned> distribution{ min,max };	// 整数均匀分布	
	return bind(distribution, generator);
}
// 生成伪随机实数，左闭右开区间
double Pseudo_random_number(double min, double max)
{
	using std::random_device, std::default_random_engine, std::uniform_real_distribution;
	random_device seeder;										// 真随机数作为种子
	default_random_engine generator{ seeder() };					// 伪随机数生成器
	uniform_real_distribution<double> distribution{ min,max };	// 实数均匀分布	
	return distribution(generator);
}
// 伪随机数生成器PRNG,实数类，左闭右开区间
auto create_pseudo_random_number_generator(double min, double max)
{
	using std::random_device, std::default_random_engine, std::uniform_real_distribution, std::bind;
	random_device seeder;										// 真随机数作为种子
	default_random_engine generator{ seeder() };				// 伪随机数生成器
	uniform_real_distribution<double> distribution{ min,max };	// 实数均匀分布	
	return bind(distribution, generator);
}
 
// 函数模板，实现交换两个基本类型的值
template<typename T>
void swap(T& left, T& right)
{
	T temp{ left };
	left = move(right);
	right = move(temp);
}
 
 
// 初始化种群
void Genetic_Algorithm::initialize()
{
	Mutation_P = 1.0 / 1024;
	m_population.reserve(Po_Size);
	for (size_t i{}; i < Po_Size; ++i)
	{
		vector<int>dna{};
		dna.reserve(Customer::Size - 1ull);
		for (int gen{ 1 }; gen < Customer::Size; ++gen)
		{
			dna.push_back(gen);
		}
		auto random_index{ create_pseudo_random_number_generator(0u,Customer::Size - 2u) };
		for (int times{}; times < Customer::Size; ++times)
		{
			swap(dna[random_index()], dna[random_index()]);
		}
		m_population.push_back(Individual{ dna });
	}
}
// 获得适应度
void Genetic_Algorithm::get_fitness()
{
	for (Individual& individual:m_population)
	{
		individual.decode();
		individual.Update_and_display_solutions();
		individual.update_fitness();
		if (individual.get_number_of_violations() > 0)
		{
			unsigned punish_times{ individual.get_number_of_violations() };
			individual.multiply_fitness(Punish, punish_times);
		}	
	}
}
// 获得遗传概率
void Genetic_Algorithm::get_genetic_probability()
{
	double sum{};
	for (const Individual& individual : m_population)
	{
		sum += individual.get_fitness();
	}
	for (Individual& individual : m_population)
	{
		individual.set_genetic_probability(individual.get_fitness() / sum);
	}
}
// 获得轮盘赌累加概率
void Genetic_Algorithm::get_sum_probability()
{
	for (double sum{}; Individual& individual : m_population)
	{
		sum += individual.get_genetic_probability();
		individual.set_sum_probability(sum);
	}
	m_population.back().set_sum_probability(1.0);	// 最后一个体，轮盘赌值为1,消除double类型的误差
}
 
 
// 遗传算子 //
 
// 选择算子,轮盘赌多选法
void Genetic_Algorithm::selection()
{
	vector<unsigned> son_number(Po_Size,0); // 索引对应的子代数量
	static auto random{ create_pseudo_random_number_generator(0.0,1.0) };
	double point{ random() };
	const double add_number{ 1.0 / Po_Size };
	for (size_t times{}, next_index{}; times < Po_Size; ++times)
	{
		for (size_t index{ next_index }; index < Po_Size; ++index)
		{
			if (point < m_population[index].get_sum_probability())
			{
				next_index = index;
				++son_number[index];
				point += add_number;
				if (point > 1.0) 
				{
					--point;
					next_index = 0;
				}
				break;
			}
		}
	}
	vector<Individual> son_population{};
	son_population.reserve(Po_Size);
	for (size_t index{}; index < Po_Size; ++index)
	{
		for (unsigned times{}; times < son_number[index]; ++times)
		{
			son_population.push_back(m_population[index]);
		}
	}
	m_population = move(son_population);
}
// 交叉算子，两点交叉+映射法
void Genetic_Algorithm::crossover()
{
	using std::pair, std::make_pair;
	// spouse：配偶,夫妻
	auto random_spouse_index{ create_pseudo_random_number_generator(0u, static_cast<unsigned>(Po_Size) - 1u) };
	auto random_cross_point_index{ create_pseudo_random_number_generator(0u, Customer::Size - 2u) };
	for (size_t spouse{}; spouse < Po_Size / 2; ++spouse)
	{
		if (Pseudo_random_number(0, 1.0) < Crossover_P)
		{
			// 开始交叉
			Individual& father{ m_population[random_spouse_index()] };
			Individual& mother{ m_population[random_spouse_index()] };
			// 交叉点位置
			size_t cross_point_left{ random_cross_point_index() };	
			size_t cross_point_right{ random_cross_point_index() };
			if (cross_point_left > cross_point_right) { swap(cross_point_left, cross_point_right); }
			vector<pair<int, int>> Map_from_father_to_mother{};
			Map_from_father_to_mother.reserve(cross_point_right - cross_point_left + 1);
			// 交换基因
			for (size_t cross_point{ cross_point_left }; cross_point <= cross_point_right; ++cross_point)
			{
				int& father_gen{ father[cross_point] };
				int& mother_gen{ mother[cross_point] };
				Map_from_father_to_mother.push_back(make_pair(father_gen, mother_gen));
				swap(father_gen, mother_gen);
			}
			// 映射
			for (const pair<int,int>& map : Map_from_father_to_mother)
			{
				for (int& gen : father.set_DNA())
				{
					if (int switch_gen{ map.first }; gen == map.second)
					{
						swap(gen, switch_gen);
						break;
					}
				}
				for (int& gen : mother.set_DNA())
				{
					if (int switch_gen{ map.second }; gen == map.first)
					{
						swap(gen, switch_gen);
						break;
					}
				}
			}
		}
	}
}
// 变异算子，两点交换变异
void Genetic_Algorithm::mutation()
{
	static auto random{ create_pseudo_random_number_generator(0.0, 1.0) };
	auto random_exchange_point{ create_pseudo_random_number_generator(0u, Customer::Size - 2u) };
	for (auto& individual : m_population)
	{
		if (random() < Mutation_P)
		{
			// 开始变异
			swap(individual[random_exchange_point()], individual[random_exchange_point()]);
		}
	}
}
// 遗传算子 //
 
// 遗传算法入口
void Genetic_Algorithm::genetic_algorithm()
{
	// 初始化种群
	initialize();
	for (size_t generation{}; generation <= Iterations; ++generation)
	{
		if (generation % 10ull == 0)
		{
			cout << format("{:->50}{:^5}{:-<50}\n", "第", generation, "代");
		}
		// 获得适应度
		get_fitness();
		// 获得遗传概率
		get_genetic_probability();
		// 获得轮盘赌累加概率
		get_sum_probability();
 
		// 遗传算子 //
 
		// 选择算子，轮盘赌多选法
		selection();
		// 交叉算子，两点交叉+映射法
		crossover();
		// 变异算子，两点交换变异
		mutation();
 
		// 遗传算子 //
 
		// 遗传概率调整
		if ((generation + 1) % 128ull == 0)
		{
			static auto random_0_to_1{ create_pseudo_random_number_generator(0.0,1.0) };
			Crossover_P = random_0_to_1();
			static const double mutation_probability_Increase{ (1.0 - Mutation_P) / Iterations * 64 };
			Mutation_P += mutation_probability_Increase;
			cout << "交叉概率:" << Crossover_P
				<< "\n变异概率:" << Mutation_P << "\n";
		}
	}
	get_fitness();
	Best_Individual_in_History.decode();
	Best_Individual_in_History.update_cost();
	if (Individual::Best_Individuals.size() == 1)
	{
		cout << "\n找到唯一最优解:\n";
		Individual::Best_Individuals.front().show_individual();
		if (Individual::Best_Individuals.front().get_DNA() == Best_Individual_in_History.get_DNA())
		{
			cout << "\n本次最优解与历史最优解目标值相同!\n";
		}
		else
		{
			cout << "\n历史最优解:\n";
			Best_Individual_in_History.show_individual();
		}
	}
	else if (Individual::Best_Individuals.size() > 1)
	{
		cout << "\n找到多个最优解:\n";
		for (const auto& best_individual : Individual::Best_Individuals)
		{
			best_individual.show_individual();
		}
		if (Individual::Best_Individuals.front().get_cost() == Best_Individual_in_History.get_cost())
		{
			cout << "\n本次最优解与历史最优解目标值相同!\n";
		}
		else
		{
			cout << "\n历史最优解:\n";
			Best_Individual_in_History.show_individual();
		}
	}
}
 
// 展示固有参数
void Genetic_Algorithm::show_parameters(int choice)
{
	if (choice == 0)
	{
		cout << format("{:12}{:^6}\n{:12}{:^6}\n{:12}{:^6}\n{:12}{:^6}\n{:12}{:^6}\n",
			"种群规模:", Po_Size,
			"进化代数:", Iterations,
			"交叉概率:", Crossover_P,
			"变异概率:", Mutation_P,
			"惩罚系数:", Punish);
	}
	else if (choice == 1)
	{
		cout << format("{:12}{:^6}\n{:12}{:^6}\n{:12}{:^6}\n{:12}{:^6}\n",
			"6.种群规模:", Po_Size,
			"7.进化代数:", Iterations,
			"8.交叉概率:", Crossover_P,
			"9.变异概率:", Mutation_P);
	}
}

//UI_Manage.cpp
#include "UI_Manage.h"
 
 
#include<iostream>
#include<format>
#include<fstream>
#include<Windows.h>
 
using
std::string_view, std::string,
std::cout, std::endl,
std::format;
 
 
 
// 展示菜单 
void UI_Manage::Show_Menu()const
{
	cout << format("{:*^30}\n{:*^30}\n{:*^30}\n{:*^30}\n{:*^30}\n{:*^30}\n{:*^30}\n{:*^30}\n{:*^30}\n", 
		""
		," 遗传算法v1.0 "
		," by : 雷海泷  "
		,"0.    退出    "
		,"1.   读取文件 "
		,"2.  展示参数  "
		,"3.展示文件路径"
		,"4.  开始求解  "
		,"5.  修改参数  "
		,"");
}
 
// 读取文件1
bool UI_Manage::read_file(string_view distance_file, string_view time_file, string_view customer_file)
{
	using std::ifstream, std::ios, std::vector, std::array, std::move;
	ifstream distance_ifs{ string{distance_file},ios::in };
	ifstream time_ifs{ string{time_file},ios::in };
	ifstream customer_ifs{ string{customer_file},ios::in };
	char buf[100]{};
	GetCurrentDirectoryA(100, buf);
	if (!distance_ifs.is_open())
	{
		cout << format("文件{}\\{}打开失败!\n", buf, distance_file);
		time_ifs.close();
		customer_ifs.close();
		return false;
	}
	else if (!time_ifs.is_open())
	{
		cout << format("文件{}\\{}打开失败!\n", buf, time_file);
		distance_ifs.close();
		customer_ifs.close();
		return false;
 
	}
	else if (!customer_ifs.is_open())
	{
		cout << format("文件{}\\{}打开失败!\n", buf, customer_file);
		distance_ifs.close();
		time_ifs.close();
		return false;
	}
	else
	{
		Customer::Distance_Matrix.clear();
		Car::Time_Matrix.clear();
		Customer::Customer_Array.clear();
		Customer::Customer_Array.push_back(move(Customer{}));
		unsigned number, requirement, time_start1, time_end1, time_start2, time_end2;
		double service_time;
		while (customer_ifs >> number
			&& customer_ifs >> requirement
			&& customer_ifs >> service_time
			&& customer_ifs >> time_start1
			&& customer_ifs >> time_end1
			&& customer_ifs >> time_start2
			&& customer_ifs >> time_end2)
		{
			Customer::Customer_Array.push_back(move(Customer{ number,requirement,service_time, array<Time, Window_num> { Time{ time_start1, time_end1 }, Time{ time_start2, time_end2 } } }));
		}
		Customer::Size = static_cast<int>(Customer::Customer_Array.size());
		cout << format("文件{}\\{}读取成功!\n", buf, customer_file);
		customer_ifs.close();
		for (size_t i{}; i < Customer::Size; ++i)
		{
			vector<int> distance_row{};
			int distance;
			for (size_t j{}; j < Customer::Size && distance_ifs >> distance; ++j)
			{
				distance_row.push_back(distance);
			}
			Customer::Distance_Matrix.push_back(move(distance_row));
			vector<double> time_row{};
			double time;
			for (size_t j{}; j < Customer::Size && time_ifs >> time; ++j)
			{
				time_row.push_back(time);
			}
			Car::Time_Matrix.push_back(move(time_row));
		}
		cout << format("文件{}\\{}读取成功!\n", buf, distance_file);
		distance_ifs.close();
		cout << format("文件{}\\{}读取成功!\n", buf, time_file);
		time_ifs.close();
		m_file_read = true;
		return true;
	}
}
// 展示所有参数2
void UI_Manage::show_all_parameters()const
{
	if (!m_file_read)
	{
		cout << "未读取文件!\n";
		system("pause");
	}
	else
	{
		// Customer
		cout << format("{:-^30}\n", "客户与配送中心参数");
		Customer::show_parameters();
		// Car
		cout << format("{:-^30}\n", "车辆参数");
		Car::show_parameters();
 
		// Genetic_Algorithm
		cout << format("{:-^30}\n", "遗传算法参数");
		Genetic_Algorithm::show_parameters();
	}
 
}
 
// 展示文件路径3
void UI_Manage::show_file_path()const
{
	char buf[100]{};
	GetCurrentDirectoryA(100, buf);
	cout << format("{}:{}\\\n", "当前路径", buf);
}
 
// 开始求解4
void UI_Manage::start_solve(string_view distance_file, string_view time_file, string_view customer_file)
{
	if (!m_file_read)
	{
		cout << "未读取文件!\n";
		system("pause");
		return;
	}
	read_file(distance_file, time_file, customer_file);
	Genetic_Algorithm GA{};
	LARGE_INTEGER start_time, end_time, frequency;
	QueryPerformanceFrequency(&frequency);
	QueryPerformanceCounter(&start_time);
 
	GA.genetic_algorithm();
 
	QueryPerformanceCounter(&end_time);
	long long run_time{ (end_time.QuadPart - start_time.QuadPart) * 1'000 / frequency.QuadPart };
	long long minute{run_time / 60'000 };
	long long second{ (run_time - minute * 60'000) / 1'000 };
	long long millisecond{ run_time - minute * 60'000 - second * 1'000 };
	cout << format("{}{}{}{}{}{}{}\n", "用时 ", minute, "分", second, "秒", millisecond, "毫秒");
}
 
// 修改参数5
void UI_Manage::modify_parameters()
{
	using std::cin;
	if (!m_file_read)
	{
		cout << "未读取文件!\n";
		system("pause");
		return;
	}
	int choice{ -1 };
	while (true)
	{
		cout << "可修改的参数:\n";
		cout << format("{:}\n", "0.退出");
		Car::show_parameters(1);
		Genetic_Algorithm::show_parameters(1);
		cout << "请输入您的选择：" << endl;
		cin >> choice;
		//输入检查
		if (cin.fail())
		{
			cout << "输入错误！" << endl;
			cin.clear();
			cin.ignore(1024, '\n');
			system("pause");
			continue;
		}
		switch (choice)
		{
		case 0:// 退出
			return;
		case 1:// 1.车辆最大数量
		{
			unsigned input_value{ Car::Max_Amount };
			cout << "修改为:";
			cin >> input_value;
			//输入检查
			if (cin.fail())
			{
				cout << "输入错误！" << endl;
				cin.clear();
				cin.ignore(1024, '\n');
				system("pause");
				continue;
			}
			Car::Max_Amount = input_value;
			break;
		}
			
		case 2:// 2.车辆载重量
		{
			unsigned input_value{ Car::Max_Load };
			cout << "修改为:";
			cin >> input_value;
			//输入检查
			if (cin.fail())
			{
				cout << "输入错误！" << endl;
				cin.clear();
				cin.ignore(1024, '\n');
				system("pause");
				continue;
			}
			Car::Max_Load = input_value;
			break;
		}
		case 3:// 3.车辆最大行驶距离
		{
			unsigned input_value{ Car::Max_Distance };
			cout << "修改为:";
			cin >> input_value;
			//输入检查
			if (cin.fail())
			{
				cout << "输入错误！" << endl;
				cin.clear();
				cin.ignore(1024, '\n');
				system("pause");
				continue;
			}
			Car::Max_Distance = input_value;
			break;
		}
		case 4:// 4.车辆固定成本
		{
			unsigned input_value{ Car::Fixed_Cost };
			cout << "修改为:";
			cin >> input_value;
			//输入检查
			if (cin.fail())
			{
				cout << "输入错误！" << endl;
				cin.clear();
				cin.ignore(1024, '\n');
				system("pause");
				continue;
			}
			Car::Fixed_Cost = input_value;
			break;
		}
		case 5:// 5.车辆单位距离行驶成本
		{
			unsigned input_value{ Car::Variable_Cost };
			cout << "修改为:";
			cin >> input_value;
			//输入检查
			if (cin.fail())
			{
				cout << "输入错误！" << endl;
				cin.clear();
				cin.ignore(1024, '\n');
				system("pause");
				continue;
			}
			Car::Variable_Cost = input_value;
			break;
		}
		case 6:// 6.种群规模
		{
			size_t input_value{ Genetic_Algorithm::Po_Size };
			cout << "修改为:";
			cin >> input_value;
			//输入检查
			if (cin.fail())
			{
				cout << "输入错误！" << endl;
				cin.clear();
				cin.ignore(1024, '\n');
				system("pause");
				continue;
			}
			Genetic_Algorithm::Po_Size = input_value;
			break;
		}
		case 7:// 7.进化代数
		{
			size_t input_value{ Genetic_Algorithm::Iterations };
			cout << "修改为:";
			cin >> input_value;
			//输入检查
			if (cin.fail())
			{
				cout << "输入错误！" << endl;
				cin.clear();
				cin.ignore(1024, '\n');
				system("pause");
				continue;
			}
			Genetic_Algorithm::Iterations = input_value;
			break;
		}
		case 8:// 8.交叉概率
		{
			double input_value{ Genetic_Algorithm::Crossover_P };
			cout << "修改为:";
			cin >> input_value;
			//输入检查
			if (cin.fail())
			{
				cout << "输入错误！" << endl;
				cin.clear();
				cin.ignore(1024, '\n');
				system("pause");
				continue;
			}
			Genetic_Algorithm::Crossover_P = input_value;
			break;
		}
		case 9:// 9.变异概率
		{
			double input_value{ Genetic_Algorithm::Mutation_P };
			cout << "修改为:";
			cin >> input_value;
			//输入检查
			if (cin.fail())
			{
				cout << "输入错误！" << endl;
				cin.clear();
				cin.ignore(1024, '\n');
				system("pause");
				continue;
			}
			Genetic_Algorithm::Mutation_P = input_value;
			break;
		}
		default://输入错误
			cout << "输入错误!" << endl;
			system("pause");
			break;
		}
		system("cls");
	}
}

// 遗传算法v1.0.cpp
#include<iostream>
#include<format>
#include<Windows.h>
 
#include"UI_Manage.h"
 
using
std::cout, std::cin,std::endl,
std::format,
std::vector, std::array;
 
 
 
 
 
 
int main()
{
	try
	{
		UI_Manage ui;
		int choice{ -1 };
		while (true)
		{
			ui.Show_Menu();
			cout << "请输入您的选择：" << endl;
			cin >> choice;
			//输入检查
			if (cin.fail())
			{
				cout << "输入错误！即将返回菜单！" << endl;
				cin.clear();
				cin.ignore(1024, '\n');
				system("pause");
				continue;
			}
 
			switch (choice)
			{
			case 0:// 退出程序
				ui.exit_system();
				break;
			case 1:// 读取文件
				ui.read_file();
				system("pause");
				break;
			case 2:// 展示所有参数
				ui.show_all_parameters();
				system("pause");
				break;
			case 3:// 展示当前路径
				ui.show_file_path();
				system("pause");
				break;
			case 4:// 开始求解
				ui.start_solve();
				system("pause");
				break;
			case 5:// 修改参数
				ui.modify_parameters();
				break;
			default:// 输入错误
				cout << "输入错误！即将返回菜单！" << endl;
				system("pause");
				break;
			}
			system("cls");
		}
		return 0;
	}
	catch (const std::exception& trouble)
	{
		cout << "发生异常:" << trouble.what() << endl;
		system("pause");
	}
}

6.程序结果：

（1）初始界面：

 （2）程序参数（可修改）

 （3）求解结果