python tsp 求解VRP问题的经典算法

求解VRP问题的经典算法，实现运算，源程序代码，含注释，可以自己修改数据

“““
@author: zll
description：
迭代局部搜索算法求解TSP
“““

import random
import time
import math
import copy

max_iterations = 10
max_no_improve = 10
CITY_SIZE = 52 #城市数量

# 柏林52城算例
city = [
[ 565575 ][ 25185 ][ 345750 ][ 945685 ][ 845655 ]
[ 880660 ][ 25230 ][ 5251000 ][ 5801175 ][ 6501130 ]
[ 1605620 ][ 1220580 ][ 1465200 ][ 15305 ]
[ 845680 ][ 725370 ][ 145665 ]
[ 415635 ][ 510875 ][ 560365 ][ 300465 ][ 520585 ][ 480415 ]
[ 835625 ][ 975580 ][ 1215245 ][ 1320315 ][ 1250400 ][ 660180 ]
[ 410250 ][ 420555 ][ 575665 ][ 11501160 ][ 700580 ][ 685595 ]
[ 685610 ][ 770610 ][ 795645 ][ 720635 ][ 760650 ][ 475960 ]
[ 95260 ][ 875920 ][ 700500 ][ 555815 ][ 830485 ][ 117065 ]
[ 830610 ][ 605625 ][ 595360 ][ 1340725 ][ 1740245 ]
	];

#优化值
Delta = [ [0 for i in range（CITY_SIZE）] for j in range（CITY_SIZE） ]


class Solution:
	def __init__（self）:
		self.cost = 0
		self.route = []
	
	def copy（self）:
		solution = Solution（）
		solution.cost = self.cost
		solution.route = copy.deepcopy（self.route）
		return solution


def ILS（）:

	#计算路径总长度
	def cost_total（city_list）:
		cost = 0
		for i in range（CITY_SIZE - 1）:
			cost += distance_2city（city_list[i] city_list[i + 1]）
		cost += distance_2city（city_list[CITY_SIZE - 1] city_list[0]）
		return cost


	#计算两个城市间距离
	def distance_2city （c1 c2）:
		dis = math.sqrt（（city[c1][0] - city[c2][0]） ** 2 + （city[c1][1] - city[c2][1]） ** 2）
		return dis


	#本地局部搜索，找出局部最优解，边界条件 max_no_improve
	def local_search（best_solution）:

		#颠倒数组中下标begin到end的元素位置
		def swap_element（city_list begin end）:
			while  begin < end :
				temp = city_list[begin]
				city_list[begin] = city_list[end]
				city_list[end] = temp
				begin += 1
				end -= 1

		#邻域动作 反转index_i <-> index_j 间的元素
		def two_opt_swap（cities_route index_i index_j）:
			new_cities_route = copy.deepcopy（cities_route）
			swap_element（new_cities_route index_i index_j）
			return new_cities_route

		# 计算邻域操作优化值 
		def calc_delta（i k city_list）:
			‘‘‘
                以下计算说明：
                对于每个方案，翻转以后没必要再次重新计算总距离
                只需要在翻转的头尾做个小小处理

                比如：
                有城市序列   1-2-3-4-5 总距离 = d12 + d23 + d34 + d45 + d51 = A
                翻转后的序列 1-4-3-2-5 总距离 = d14 + d43 + d32 + d25 + d51 = B
                由于 dij 与 dji是一样的，所以B也可以表示成 B = A - d12 - d45 + d14 + d25
                下面的优化就是基于这种原理
			‘‘‘

			delta = 0

			if i == 0 and k == CITY_SIZE - 1 :
				delta = 0
			else :
				i2 = （i - 1 + CITY_SIZE） % CITY_SIZE
				k2 = （k + 1） % CITY_SIZE 
				delta = 0 
				- distance_2city（city_list[i2] city_list[i]） 
				+ distance_2city（city_list[i2] city_list[k]） 
				- distance_2city（city_list[k] city_list[k2]） 
				+ distance_2city（city_list[i] city_list[k2]） 

			return delta

		# 更新Delta 
		def Update（i k route） :
			‘‘‘
		小编注：这是一个计算每次领域动作后路径长度改变值的小优化，在测试中我们暂时

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        7738  2020-11-27 13:02  python tsp\ILS TSP.py
     文件        2479  2020-11-27 13:02  python tsp\SA TSP.py
     文件        6965  2020-11-27 13:02  python tsp\TS TSP.py