【BI学习心得21-常见规划问题2】

2023-09-29 14:15:40

1.旅行商问题

Travelling Salesman Problem，一个旅行商想去拜访若干城市，然后回到他的出发地，给定各个城市之间所需的旅行时间后，怎样计划他的路线，使得他能对每个城市恰好进行一次访问，而且总时间最短。

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

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

由此定义不难看出，旅行商问题（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaery[2]已证明TSP问题是NP难题，因此，VRP也属于NP难题。

车辆路线问题自1959年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。车辆路线问题可以描述如下（如图）：

设有一场站（depot），共有M 辆货车，车辆容量为Q，有N位顾客（customer），每位顾客有其需求量D。车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。

2.1问题类型

一般而言车辆路线问题大致可以分为以下三种类型（Ballou，1992）：

相异的单一起点和单一终点
相同的单一起点和终点
多个起点和终点

2.2车辆路径问题的方法

关于车辆路线问题之学术研究文献众多，也提出了相当多的求解策略与方法，Bodin and Golden（1981）将众多之求解方法归纳成以下七种：

2.3求解方法

1、求解方法演进

综合过去有关车辆路线问题的求解方法，可以分为精确算法（exact algorithm）与启发式解法（heuristics），其中精密算法有分支界限法、分支切割法、集合涵盖法等；启发式解法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁殖民算法等。1995年，Fisher[5]曾将求解车辆路线问题的算法分成三个阶段。第一阶段是从1960年到1970年，属于简单启发式方式，包括有各种局部改善启发式算法和贪婪法（Greedy）等；第二阶段是从1970年到1980年，属于一种以数学规划为主的启发式解法，包括指派法、集合分割法和集合涵盖法；第三阶段是从1990开始至今，属于较新的方法，包括利用严谨启发式方法、人工智能方法等。

2、启发式算法
由于VRP是NP-hard问题，难以用精确算发求解，启发式算法是求解车辆运输问题的主要方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式方法。车辆运输问题的启发式方法可以分为简单启发式算法、两阶段启发式算法、人工智能方法建立的启发式方法。

简单启发式方法包括节省法或插入法、路线内／间节点交换法、贪婪法和局部搜索法等方法。节省法或插入法（savings or insertion）是在求解过程中使用节省成本最大的可行方式构造路线，直到无法节省为止。交换法则是依赖其他方法产生一个起始路线，然后以迭代的方式利用交换改善法减少路线距离，直到不能改善为止。1960年，Clarke和Wright[6]首先提出一种启发式节省法（savings methods）来建立车队配送路线。简单启发式方法简单易懂、求解速度快，但只适合求解小型、简单的VRP问题。

两阶段方法包括先分组后定路线（clusterfirst-route second）和先定路线后分组（routefirst-cluster second）两种启发式策略。前者是先将所有需求点大略分为几个组，然后再对各个组分别进行路线排序；后者则是先将所有的需求点建构成一条路线，再根据车辆的容量将这一路线分割成许多适合的单独路线。

1990年以来，人工智能方法在解决组合优化问题上显示出强大功能，在各个领域得到充分应用，很多学者也将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法。禁忌搜索法（TS）基本上是属于一种人工智能型（AI）的局部搜寻方法，Willard首先将此算法用来求解VRP ，随后亦有许多位学者也发表了求解VRP的TS 算法。西南交通大学的袁庆达[7]等设计了考虑时间窗口和不同车辆类型的禁忌算法，这种算法主要采用GENIUS方法产生初始解，然后禁忌算法对初始解优化。模拟退火方法具有收敛速度快，全局搜索的特点，Osman[8]对VRP的模拟退火算法进行了研究，他提出的模拟退火方法主要适合于解决路线分组。遗传算法具有求解组合优化问题的良好特性，Holland首先采用遗传算法（GA）编码解决VRPTW 问题。现在多数学者采用混合策略，分别采用两种人工智能方法进行路线分组和路线优化。Ombuki[9]提出了用遗传算法进行路线分组，然后用禁忌搜索方法进行路线优化的混合算法。Bent和Van Hentenryck则首先用模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法（largneighborhood search）将运输费用降到最低。

3.遗传算法

遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，通过模拟自然进化过程搜索最优解。

遗传算法是从首先是初始化一个种群，然后根据适应性函数确定个体的适应度，由适应度来选择个体进行交叉，以某种概率让个体进行变异，从而不断选出适应度高的个体，进而更新种群。

其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向。

遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

遗传算法一共有下面几个步骤：

初始化：设置进化代数计数器 t=0、设置最大进化代数 T、交叉概率、变异概率、随机生成 M 个个体作为初始种群 P
个体评价：计算种群 P 中各个个体的适应度
选择运算：将选择算子作用于群体。以个体适应度为基础，选择最优个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代
交叉运算：在交叉概率的控制下，对群体中的个体两两进行交叉
变异运算：在变异概率的控制下，对群体中的个体两两进行变异，即对某一个体的基因进行随机调整
经过选择、交叉、变异运算之后得到下一代群体 P’

代码和数据下载链接：https://pan.baidu.com/s/1Tu5ZFPm2ZbITz6f8Jiyg9Q
提取码：91g1

具体代码：

import numpy as np
import random
import copy
import matplotlib.pyplot as plt
 
class City:
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
    def __repr__(self):
        return "(" + str(self.x) + "," + str(self.y) + ")"
 
def distance(ca, cb):
    dx = abs(ca.x - cb.x)
    dy = abs(ca.y - cb.y)
    distance = np.sqrt((dx ** 2) + (dy ** 2))
    return distance
 
def init_pop(city_list, popSize):
    pop = []
    for i in range(popSize):
        new_city_list = random.sample(city_list, len(city_list))
        pop.append(new_city_list)
 
    return pop
 
def fitness(pop):
    dis_citys = distance_citys(pop)
    return 1.0/dis_citys
 
def distance_citys(pop):
    temp_dis = 0
    for i in range(len(pop)-1):
        temp_dis += distance(pop[i], pop[i+1])
    temp_dis += distance(pop[len(pop)-1], pop[0])
 
    return temp_dis
 
def rank(poplulation):
    rankPop_dic = {}
    for i in range(len(poplulation)):
        fit = fitness(poplulation[i])
        rankPop_dic[i] = fit
 
    return sorted(rankPop_dic.items(), key=lambda x:x[1], reverse=True)
 
 
def select(pop, pop_rank, eliteSize):
    select_pop = []
    for i in range(eliteSize):
        select_pop.append(pop[pop_rank[i][0]])
 
    cumsum = 0
    cumsum_list = []
    temp_pop = copy.deepcopy(pop_rank)
    for i in range(len(temp_pop)):
        cumsum += temp_pop[i][1]
        cumsum_list.append(cumsum)
    for i in range(len(temp_pop)):
        cumsum_list[i] /= cumsum
 
    for i in range(len(temp_pop)-eliteSize):
        rate = random.random()
        for j in range(len(temp_pop)):
            if cumsum_list[j] > rate:
                select_pop.append(pop[pop_rank[i][0]])
                break
 
    return select_pop
 
def breed(pop, eliteSize):
    breed_pop = []
    for i in range(eliteSize):
        breed_pop.append(pop[i])
 
    i = 0
    while i < (len(pop)-eliteSize):
        a = random.randint(0, len(pop)-1)
        b = random.randint(0, len(pop)-1)
        if a != b:
            fa, fb = pop[a], pop[b]
            genea, geneb = random.randint(0, len(pop[a])-1), random.randint(0, len(pop[b])-1)
            startgene = min(genea, geneb)
            endgene = max(genea, geneb)
            child1 = []
            for j in range(startgene, endgene):
                child1.append(fa[j])
            # child1 = copy.deepcopy(fa[:-1])
            child2 = []
            for j in fb:
                if j not in child1:
                    child2.append(j)
            # child2 = [j for j in fb if j not in child1]
            breed_pop.append(child1+child2)
            i = i+1
 
    return breed_pop
 
def mutate(pop, mutationRate):
    mutation_pop = []
    for i in range(len(pop)):
        for j in range(len(pop[i])):
            rate = random.random()
            if rate < mutationRate:
                a = random.randint(0, len(pop[i])-1)
                pop[i][a], pop[i][j] = pop[i][j], pop[i][a]
        mutation_pop.append(pop[i])
 
    return mutation_pop
 
 
def next_pop(population, eliteSize, mutationRate):
    pop_rank = rank(population) #按照适应度排序
    select_pop = select(population, pop_rank, eliteSize) #精英选择策略，加上轮盘赌选择
    breed_pop = breed(select_pop, eliteSize) #繁殖
    next_generation = mutate(breed_pop, mutationRate) #变异
 
    return next_generation
 
#画出路线图的动态变化
def GA_plot_dynamic(city_list, popSize, eliteSize, mutationRate, generations):
    plt.figure('Map')
    plt.ion()
    population = init_pop(city_list, popSize)
 
    print("initial distance:{}".format(1.0/(rank(population)[0][1])))
    for i in range(generations):
        plt.cla()
        population = next_pop(population, eliteSize, mutationRate)
        idx_rank_pop = rank(population)[0][0]
        best_route = population[idx_rank_pop]
        city_x = []
        city_y = []
        for j in range(len(best_route)):
            city = best_route[j]
            city_x.append(city.x)
            city_y.append(city.y)
        city_x.append(best_route[0].x)
        city_y.append(best_route[0].y)
        plt.scatter(city_x, city_y, c='r', marker='*', s=200, alpha=0.5)
        plt.plot(city_x, city_y, "b", ms=20)
        plt.pause(0.1)
 
    plt.ioff()
    plt.show()
 
 
 
    print("final distance:{}".format(1.0 / (rank(population)[0][1])))
    bestRouteIndex = rank(population)[0][0]
    bestRoute = population[bestRouteIndex]
    return bestRoute
 
def GA(city_list, popSize, eliteSize, mutationRate, generations):
    population = init_pop(city_list, popSize) #初始化种群
    process = []
 
    print("initial distance:{}".format(1.0/(rank(population)[0][1])))
    for i in range(generations):
        population = next_pop(population, eliteSize, mutationRate) #产生下一代种群
        process.append(1.0 / (rank(population)[0][1]))
 
 
 
    plt.figure(1)
    print("final distance:{}".format(1.0 / (rank(population)[0][1])))
    plt.plot(process)
    plt.ylabel('Distance')
    plt.xlabel('Generation')
    plt.savefig(str(generations)+ '_' + str(1.0 / (rank(population)[0][1])) + '_' + str(mutationRate) +'_process.jpg')
 
    plt.figure(2)
    idx_rank_pop = rank(population)[0][0]
    best_route = population[idx_rank_pop]
    city_x = []
    city_y = []
    for j in range(len(best_route)):
        city = best_route[j]
        city_x.append(city.x)
        city_y.append(city.y)
    city_x.append(best_route[0].x)
    city_y.append(best_route[0].y)
    plt.scatter(city_x, city_y, c='r', marker='*', s=200, alpha=0.5)
    plt.plot(city_x, city_y, "b", ms=20)
 
    plt.savefig(str(generations)+'_' + str(mutationRate) + '_route.jpg')
    plt.show()
 
num_city = 25
city_list = []
 
 
# for i in range(num_city):
#     x = random.randint(1, 200)
#     y = random.randint(1, 200)
#     city_list.append(City(x, y))
with open('city.txt', 'r', encoding='UTF-8') as f:
    lines = f.readlines()
for line in lines:
    line = line.replace('\n', '')
    # line = line.replace('\t', '')
    city = line.split('\t')
    city_list.append( City( float(city[1]), float(city[2]) ) )
 
# mutationRates = [0.001, 0.002, 0.005, 0.008, 0.01, 0.02]
# for mut in mutationRates:
GA(city_list, 100, 20, 0.01, 5000)

结果如下：

码农公寓

【BI学习心得21-常见规划问题2】

目录

1.旅行商问题

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

2.1问题类型

2.2车辆路径问题的方法

2.3求解方法

3.遗传算法

码农公寓

目录

1.旅行商问题

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

2.1问题类型

2.2车辆路径问题的方法

2.3求解方法

3.遗传算法

相关文章