python实现VRPTW求解禁忌搜索算法

python实现VRPTW求解禁忌搜索+变邻域搜索代码，完美支持所罗门算例！

# -*- coding: utf-8 -*-
“““
Created on Tue Mar  6 20:07:55 2018

@author: Dylan
“““

import numpy as np
import random
import copy
#random.seed（1）

class Node（object）:
    ‘‘‘
    顾客点类：
    c_id:Number顾客点编号
    x:Number点的横坐标
    y:Number点的纵坐标
    demand:Number点的需求量
    ready_time:Number点的最早访问时间
    due_time:Number点的最晚访问时间
    service_time:Number点的服务时间
    belong_veh:所属车辆编号
    ‘‘‘
    def __init__（selfc_idxydemandready_timedue_timeservice_time）:
        self.c_id = c_id
        self.x = x
        self.y = y
        self.demand = demand
        self.ready_time = ready_time
        self.due_time = due_time
        self.service_time = service_time        
        self.belong_veh = None

class Vehicle（object）:
    ‘‘‘
    车辆类：
    v_id:Number车辆编号
    cap:Number车的最大载重量
    load:Number车的载重量
    distance:Number车的行驶距离
    violate_time:Number车违反其经过的各点时间窗时长总和
    route:List车经过的点index的列表
    start_time:List车在每个点的开始服务时间
    ‘‘‘ 
    
    def __init__（selfv_id:intcap:int）:
        self.v_id = v_id
        self.cap = cap
        self.load = 0
        self.distance = 0
        self.violate_time = 0
        self.route = [0]
        self.start_time = [0]
        
    #插入节点
    def insert_node（selfnode:intindex:int = 0） -> None:
        if index == 0:
            self.route.append（node）
        else:
            self.route.insert（indexnode）
        #node.belong_veh = self.v_id
        self.update_info（）
    
    #根据索引删除节点
    def del_node_by_index（selfindex:int） -> None:
        self.route.pop（index）
        self.update_info（）
        
    #根据对象删除节点
    def del_node_by_node（selfnode:Node） -> None:
        self.route.remove（node.c_id）
        self.update_info（）
        
    #更新载重、距离、开始服务时间、时间窗违反
    def update_info（self） -> None:
        #更新载重
        cur_load = 0
        for n in self.route:
            cur_load += nodes[n].demand
        self.load = cur_load
        #更新距离
        cur_distance = 0
        for i in range（len（self.route）-1）: 
            cur_distance += distance_matrix[self.route[i]][self.route[i+1]]
        self.distance = cur_distance
        #更新违反时间窗时长总和（硬时间窗早到等待，不可晚到）
        arrival_time = 0
        self.start_time = [0]
        cur_violate_time = 0
        for i in range（1len（self.route））: 
            arrival_time += distance_matrix[self.route[i-1]][self.route[i]] + nodes[self.route[i-1]].service_time
            if arrival_time > nodes[self.route[i]].due_time:
                cur_violate_time += arrival_time - nodes[self.route[i]].due_time
            elif arrival_time < nodes[self.route[i]].ready_time:
               arrival_time = nodes[self.route[i]].ready_time 
            self.start_time.append（arrival_time）
        self.violate_time = cur_violate_time

    def __str__（self）:#重载print（）
        routes = [n for n in self.route]
        return ‘车{}:距离[{:.4f}];载重[{}];时间违反[{:.4f}]\n路径{}\n开始服务时间{}\n‘.format（self.v_

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-04-25 09:16  python实现VRPTW求解禁忌搜索算法\
     文件       30272  2018-03-08 18:59  python实现VRPTW求解禁忌搜索算法\vrptw2.py
     目录           0  2018-04-25 09:16  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\
     目录           0  2018-04-25 09:16  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C101.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C102.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C103.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C104.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C105.txt
     文件        7520  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C106.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C107.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C108.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C109.txt
     文件        7522  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C201.txt
     文件        7524  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C202.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C203.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C204.txt
     文件        7524  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C205.txt
     文件        7525  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C206.txt
     文件        7524  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C207.txt
     文件        7524  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\C208.txt
     文件        7321  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\R101.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\R102.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\R103.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\R104.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\R105.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\R106.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\R107.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\R108.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\R109.txt
     文件        7523  1998-03-05 08:35  python实现VRPTW求解禁忌搜索算法\VRPTW_solomon\solomon_100\R110.txt
............此处省略145个文件信息