物流网络选址与路径优化问题的模型与启发式解法
物流网络选址与路径优化问题的模型与启发式解法120交通运输工程学报2006年(i∈T)(10表1小规模问题的计算结果Tab. 1 Computation result of smalF-scaled problem(xh+xbk)-z≤1(i∈T,∈Ck∈K)(11)最优解∈TUC(j∈C问题规模目标值运行时间/s(12)NG= 3, NT=3, Nc= 83885k≤s1(≤c1121=∑体k∈(13NG=3,Nr=3,Nc=10421.221U-U+Nx≤N-1(i,∈S,k∈K)(14)NG=3,Nr=3,Nc=126850580∈TNG=3,NT=3,Nc=148741162000注:Nc为供应商数量,Nr为配送中心数量,Nc为客户数量ba≤B(g∈G)(16用启发式算法求得初期解xi∈/Q1(i,j∈T∪C,k∈K)(17)l0;∈/0,1∈T(18通过交换配送中心间的路径进行第1次解的改善∈/O,1∈T,j∈C)(19)yk∈/0,1(i∈C,k∈K)(20)通过交换同一路径中客户的位置(2-OPT法)进行第2次解的改善式中:G为供应商的集合;T为配送中心的集合;C为客户的集合;K为车辆的集合;Qk为车辆k的最通过交换不同路径中的客户进行第3次解的改善大载质量:S为C的部分集合;C为从点到点j的距离;B为供应商g的最大供应量;V为配送中心SA模块的最大货物通过量;D,为客户j的需求量;H2为配送中心i的固定费用;L为从供应商g到配送中是否满足终止条件心i的单位运输费用;Fk为车辆k的固定费用;a为解的输出与通过量有关的系数;xk为对于车辆k,如果点i以后的访问点是点j,即为1,否则为0;y为如果点j图1基于SA的混合启发式算法的货物由车辆k配送,即为1,否则为0;v;为如果FiMixed heuristic algorit hm based on sa使用配送中心i,即为1,否则为0;z为如果客户j传统启发式算法与智能启发式算法相结合的混合算由配送中心提供服务,即为1,否则为0;pa为从供法,以期在短时间内求得全局最优解应商g到配送中心的供应量。其中x、3计算分析和pg为决策变量。2问题的求解为了对SA的参数进行设定,进行了预备实验并确定参数如下:初始温度To为200冷却率α为为了验证上述数学模型的正确性,用数理规划07,与温度相关的循环次数调整参数β为.1,最商用软件 LINGO8.0对小规模问题进行了数值计大循环次数将按照问题规模的大小做适当的设定,算,结果见表1。可以看出,随着问题的规模扩大,数据采用人工生成数据,在200km×200km的区计算时间急剧增加;当客户达到14个时,计算时间域内随机生成指定个数的供应商、配送中心和客户,长达45h,显然无法满足解决现实问题的需要。为并生成距离矩阵和客户需求量;采用C语言编程,了满足解决现实问题的需要,有必要开发岀一种能计算结果见表2。从表2中的结果比较可以看出,够在合理的时间内求得准最优解的近似算法。表2最优解与近似解比较传统启发式算法能够在短时间内求得局部最优Tab 2 Comparison of optimal solution and approxi mate solution解,但往往容易陷于局部最优,而无法求得全局最优最优解近似解问题规模解。智能启发式算法能够求得全局最优解,但计算时目标值运行时间/s目标值运行时间/s%间相对较长。如果能够将两者结合起来,既可以防止N=3N=3,Nc=838533965求解过程陷于局部搜索无法跳出,保证全局解的搜3N=3NG=10+2122112100索,又可以缩短搜索时间达到在短时间内求得全局N-3-3Nc12|60s0620110最优解的目的。基于上述考虑本文提出了图1的将ublishrigfoustAingnsestrvcu,trttp/www.urrhi.rctNG=3,Nr=3,Nc=1487411620008895第3期陈松岩,等:物流网络选址与路径优化问题的模型与启发式解法121本算法求得的近似解与 LINGO80计算的最优解心,再从配送中心到客户这一典型的物流过程,涉及之间的误差很小,但计算时间却大大缩短了。依据运输与配送2个阶段和供应商、配送中心和客户3结果虽然无法判定所提岀的混合启发式算法对于大个层次,提出了多供应商、多物流中心情况下的物流规模问题的有效性,但可以看岀,对于求解小规模问路径与配送路径优化问题,给岀了问题的数学模型,题是有效和良好的。对于大规模问题,将利用实例利用传统启发式算法与模拟退火法开发了混合近似进行计算验证。解法,通过人工生成数据和实例计算验证,可以看出4应用实例所提出的数学模型可以准确地描述此类问题,具有良好的适应性,所提出的混合近似解法能够在短时在应用实例中,将港口作为供应商来考虑,以进间内求解问题并得到接近于最优解的近似解,具有口货物从港口经配送中心配送到客户过程中发生的较高的实用价值。但本模型没有考虑库存问题与供费用最小化为目的,以港口的数量和位置、配送中心应商的成本问题,无法达到物流网络中各个环节的数量和位置作为对象进行优化。实例的区域选择山整体优化,有待于今后进一步研究。东省,候选港口为天津港、烟台港、威海港、青岛港参考文献日照港和连云港等6处,候选配送中心设置于山东省除港口城市以外的13个地级市,设定客户分别位References于90个县(包括县级市)。为了分析候选港口和配1 I anen g Flpo C. Spatial de composit ion for a multI送中心的数量及位置与目标值之间的关系,在计算of Production Economics, 2000, 64(1/2/3): 177186过程中,候选港口和配送中心的数量分别从1开始(21 Melkote s, Das kin m s. a n in te grated model of facil ity loca tion增加(港口的位置为随机选择),计算结果见图2、3and transportat ion netw ork design[ J. Transport ation Research part A,2001,35(6):5155386[3] Goets chalckx M, Vidal C J Dogan K Modeling and design ofglobal logistics s yst ems: a review of integrated strat e gic an dt act ical models and design algorithm s[ J European Journal of005◇◇0◇◇◇◇◇◇◇Operat ional Research, 2002, 143 (1):118135791113[4] H wang H S Design of suppl y chain logist ics sy stem con sider-港口数量配送中心数量ing service level[ J. Computers and Industrial Engineerin g,图2港口数量与图3配送中心数量与2002,43(1/2):283297目标函数值关系目标函数值关系[5] WuT H, Low C, Bai J W. Heurist ic s ol ution s to mu ltt depotFig2 Relation of ob ject value Fig 3 Relation of ob ject valuelocatioN rou tin g pr ob lems[ J]. Computers and Operations Re-and ports numberand changing depots num besearch,2002,29(10):13931415可以看出,随着候选港口数量的增加.目标值呈[6 Syam ss. A model and met hodologies for the locat ion p rob lem下降趋势,说明可供选择的港口越多,求得最优解的with logist ical components[ J]. Computers and Operations Re机会越大,但本例中,当候选港口的数量增加到5个se arch,200)2,29(9):l173-1193时,目标值达到最小(实际被选中的港口为3个);候[7 Amiri A. Designing a distribution network in a suppl y chainsystem[ J]. European Jou rnal of O perat ional Research, 2004选配送中心数量的变化也呈相同的趋势,当候选配171(2):567576送中心数量达到9个时,目标值达到最小(实际被选8 G ena m, Syarif a. Hybrid genetic algorit hm for mult+ time pe-中的配送中心为8个);本实例的计算时间都在8sriod production/ distribution planning[ J1. Computers and Ir以内,虽然无法判断所求解为最优解,但从计算结果dustrial Engineering, 2005, 48(4): 799809来看,基本接近最优,因此可以认为本算法对于求解9工丰元,潘福全张丽霞等基于交通限制的路网最优路径算大规模问题也是有效和良好的法J.交通运输工程学报,2005,5(1):9295Wang Feng yuan, Pan Fuquan, Zhang Li xia, et al. Opti mal5结语path algorithm of road netw ork with traffic rest riction[ JIJourn al of Traffic and Trans port ation Engin eering, 2005, 5(1)本文将研究范围界定在商品从供应商到配送中9295.(in Ch ineseo1994-2012ChinaacAdemicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net
- 2020-12-11下载
- 积分：1
UDS_BOOTLOADER
基于ISO协议的车载CAN网络上位机诊断软件设计，一方面可了解15765的协议内容，同时，完成基于CAN通信的上位机软件开发重庆邮电人学硕士论文abstractAbstractWith the development and wide use of in-Vehicle Can (Controller AreaNetwork)network technology, complete in-vehicle can network internationaldiagnostic specification has been published. However, because of the noveltyof the specification and the protection of intellectual property rights offoreign country, our country is relatively weak on this technique, moreover,diagnostic tool is mainly dependent on high-cost foreign equipmentTherefore, the study on Can network diagnostic tool based on iso15765 withindependent intellectual property rights is significant In this paper, diagnosticstructure of certain car and network nodes which can be diagnostic is chosenas the diagnostic object. After the analysis and deep study of Iso15765architecture, low cost diagnostic upper computer of Can network is designedby vc software and USbCanii hardware acquisition card the maincontributions of dissertation include the following:(1)Basing on the research on diagnostic protocol architecture ofin-vehicle Can network the structure of in-vehicle network and thediagnostic function needs are put forward for a certain vehicle model. thediagnostic upper computer design is divided into relatively independent ofordinary diagnostic module (without download function) and downloaddiagnostic module.(2)The major 5 kinds of diagnostic services of application layer arerealized based on deep understanding of diagnostic protocol. For the networklayer data transmission, data packing algorithm which meet the Iso 15765-2is designed to achieve the network layer data package transmission.(3)Basing on the realization of the application-layer protocol and thenetwork layer data transmission algorithm. For the safety access realization,safety algorithm is designed and dLl is created. Low-cost CAn networkdiagnostic upper computer of ordinary diagnosis module is designed by VCsoftware platform and usbcanii hardware acquisition cardThe S19 file processing algorithm is designed to realize programon-line download through CAN network diagnostic specification, which isI重庆邮电大学硕士论文Abstractbased on IS015765-3 download process. Upper computer of on-line downloadis designed by VC software platform and USBCANII hardware, by whichrogram can be downloaded on-line through Can network(5)Test platform is built to test the diagnostic upper computer combinedwith CANoe. The test includes ordinary diagnostic module test and downloadfunction testTest results show that diagnostic upper computer can communicate withCAN network through IS015765, and S19 file can be downloaded on-linethrough Can successfully. The feasibility of the designed diagnostic uppercomputer is validatedKeywords: in-vehicle network, CAN, IS015765, diagnosis, testIM重庆邮电大学硕士论文第一章绪论第一章绪论1L课题研究的背景与意义CAN网络技术起源于欧洲,最早运用于汽车的电子通讯系统上,专门装备高档车型,被公认为现代B级、C级轿车和高技术含量代表的标志之山。它具有极强的抗于扰和纠错能力,这项技术的最大优点是减少了线束的数量和控制器接口的引脚数,能够使多个控制器和各类型的传感器之间的数据通信联系起来,使整车线束布置更加紧凑。CAN网络由于其非破坏性的网络仲裁机制、较高的通信速率和灵活可靠的通信方式,在车载网络领域广受青睐,CAN网络可以吏简单、迅速地实现汽车控制、通信、在线诊断以及在线编程。由于其综合的优势,目前,在多种车用总线中,CAN总线成为应用最广泛的总线。由于车载CAN总线的广泛应用,车载CAN网络的诊断技术亦显得尤为重要。由于诊断系统独立于车载CAN网络,这使得系统的开发成本增加,内部网络变得复杂。为解决上述问题,欧洲汽车厂商推出一种基于CAN总线的诊断系统通信标准ISO15765,它可满足 E-OBD(European- On Board Diagnosis)的系统要求,ISO15765以ISO142291定义的服务为基础,规定了基于CAN总线的诊断服务UdS on CAN,包括网络管理、网络定时、应用层定时等详细内容,使得该协议的适用性和可操作性更强,并与IS014230应用层的服务和参数完全兼容的。基于ISO15765的车载网络诊断不仅可以读取故障码,还能实现车载网络EC( Electronic Control Unit)的在线升级功能。通过在线升级功能,整车厂可以在4S店刷新控制器的软件,从而减少因软件缺陷造成的召回成本。此外,还能实现读取、写入及控制ECU的信息。如读取ECU的版本信息、生产厂商以及控制ECU的输入输出信息等功能。ISO15765符合现代汽车网络总线系统的发展趋势,已被许多汽车厂商采纳,并将成为未来汽车行业的通用诊断标准。对于车载网终的诊断,国外各大著名汽车公司对诊断技术的研究较为成熟,其诊断通信协议也是由国外各大厂商制定,其相关的诊断产品和诊断工具也开发的较为成熟,比如德国 Vector公司的诊断系列产品,以及 Mentor公司的诊断系列产品。目前国内的汽车生产厂商及汽车零部件厂商与研发机构大都直接使用国外相对成熟的诊断系列产品。由于知识产权的保护,国外对车载网络的诊断技术几乎处于封锁状态,即使是中外合资的相关汽车厂商或零部件厂商其诊断技术也是不会对国内开放。综上原因,使得目前国内的车载网络诊断技术处于起步阶段。因重庆邮电大学硕士论文第一章绪论此,深入研究车载网络诊断技术,是摆在国内汽车设计公司和汽车生产厂商面前必须解决的实际问题。12车载网络诊断协议概述对车载网络诊断技术的实现主要依托于对车载网络诊断协议的应用与实现。现对常用的车载网络的国际诊断协议进行概述如下Iso-9141早在1996年国际标准化组织颁布基于K线的SO9141标准:该标准的应用时间不算太长。ISo142308ISO14230于199年出台,又称作 Keyword Protocol200kw20),该诊断标准是基于K线的,波特率为104kb/s,用单线(K线)通信,也可用双线K线和L线通信,目前多用单线通信。ISO14230的头格式不是囿定的,有3或4个字节,报文传输不用分包,最大可传255个字节数据,K线本质上是一种半双工串行通信总线。过去比较常用,到目前为止,ISO14230仍是许多汽车厂商采用的诊断通信标准。报文头数据域校验和格式|目标地址源地址长度数据1数据2|……数据n校验和图111SO14230K线数据格式ISODIS 157653199年出台 ISO/DIS15765( Diagnostics on CAN-based on KWP2000,此诊断标准是基于SO14230在CAN线上的扩充,源于K线的诊断标准。So150312001年6月发布ISO15031 Communication for emissions-related diag-nostics),此诊断标准的出台主要针对排放系统相关的诊断,其中ISO15031-6中,对故障诊断码的格式进行了详细规定。so157652001年发布了IO15765 agnostics on CAN- based on UDS),此诊断标准与基于K线的诊断标准不同,这是基于统一诊断服务的诊断。其中的ISO15765-3、ISO157652分别规定了应用层与网络层的实现,在IO15765-2网络层中对ECU重庆邮电大学硕士论文第一章绪论的在线上传下载进行了详细的规定。将帧类型分为单帧、第一帧、流控帧和后续帧,此诊断标准对报文进行打包传输,数据以流控帧的机制进行传输,一次最多可传输4095字节的数据。标准CAN帧格式如图12所示。仲裁域2位控制域6位数据域64位名称|川标识符传输1符扩|1保留|数据「循环校CRC|应|帧请求/展份位0长度/数据域|验位|界定答结CRC符场|束位宽度十T40-6415图12标准cAN帧格式IsO1422912006年发布统一诊断服务标准ISO14229-1( Unified Diagnostic Services)该国际标准只是规定应用层上诊断规范,该标准的制定是为了针对任何一种连续数据链路,不涉及网络及实现未。定义诊断系统的通用需求,为了实现这一点,该标准基于OSI基本参考模型,如表11所示,其通信系统为7层。其屮映射到CAN线上的诊断为SO15765在其它链路上的映射,如无线局域网、 Flexray等的诊断,也将按照ISO1422(统一诊断标准UDS)执行。表L1诊断规范与OSI的对应关系表适性0sI7层增强诊断服务(非放射相关)遵循应用层(第7层)ISO1429l/o157653/ISo1994|5o1422更多标准ISO/IEC表达层(第6层)7498会话层(第5层IS015765-3/IS011992-4更多标准和传输层(第4层)Iso15765-2/Iso11992-4更多标准ISO/EC网络层(第3层)IsO15765-2/ISOl9924更多标准1073的7数据链路层(第2层)ISo88/S019/AE9395更多标准层物理层(第1层o898/ISo19/AE1915更多标准综述上述几种车载网络诊断协议,国内外汽车厂商使用较广泛的诊断协议为基于K线的IsO14230和基于CAN线的ISO15765诊断协议,然而随着汽车中电控电元数量的增加,如ABS系统、发送机电控系统、车身控制模块(BCM)系统、安全气囊等系统,这些系统之间以及系统与汽车仪表之间都需要进行数据交换,若这么多的数据量仍采用导线对数据进行点对点传输,则大量导线的使用会导致系统内部繁杂,且增加成本。此外,由于K线不能满足数据链路层在网络管理以重庆邮电人学硕士论文第一章绪论及通信速率上的局限性,使得K线无法满足越来越复杂的车载诊断网络的需求网随着CAN网络在汽车网络上的广泛应用,基于CAN网络的O15765的诊断则受到广泛应用,它符合现代汽车网络总线的发展趋势,逐渐被越来越多的汽车厂商使用,将成为未来汽车行业的通用诊断标准。与基于K线的ISO14230相比,基于CAN线的诊断协议ISO15765具有以下的优势(1)CAN总线的传输速率比K线要高很多,K线的传输速率为104kbt,而CAN线的最高波特率可达Mbis(2)K线使用的是单线传输,CAN线为双线采用差分信号传输,抗干扰能力强,且可靠性比K线好。(3)CAN总线可以构建比较复杂的网络结构,对于不同网络仍可通过网关实现诊断,即可实现不同网段的远程诊断,并且CAN网络的网络管理能力很强。(4)当诊断设备采用功能寻址对多个ECU进行诊断或诊断控制通信时,开发者不需考虑由于同时访问总线引起的总线冲突问题,因为CAN总线采用仲裁机制确保总线通信的正常进行。(5)利用ISO15765基于CAN线的诊断,其网络层对报文的传输进行了规范化的顺序控制以及流控制等,提高了报文传输的可靠性,并且其单次传输的报文数量可达4096字节。而K线在网络层没有定义,单次最多传输255字节的数据(6)在lSO15765-2中,明确规定了基于CAN网络的ECU在线上传下载的诊断通信流程,将上传下载纳入诊断范围内,上传下载的内容按照ISO157652网络层传输规则进行传输,以实现更标准、更可靠的网络数据传输。13国内车载CAN网络诊断存在的问题根据国内外车载网络诊断的研究现状现与目前流行的车载网络诊断协议基础,现从以下三个方面阐述目前在国内车载CAN网络诊断研究中存在的、并待解决的问题:()我国车载网络诊断技术自主知识产权方面由于基于CAN网络技术的,颖性与诊断协议本身的复杂性,现阶段国内在基于ISO15765的车载网络诊断技术的开发与应用方面尚不成熟,在诊断开发与设计方面通常借助于国外的工具或产品。目前,国内汽车制造商与设备供应商大都使用德国Ⅴ ECTOR公司的 Candelastudio、Diva、 CANdesc等诊断系列工具,由于这些诊断工具受知识产权的保护,成本较高,其整套设备需花费几十万元。因此,有必要设计开发具有自主知识产权的基于ISO15765的车载网络诊断,突破国外在重庆邮电大学硕士论文第一章绪论汽车电子行业的技术垄断,开发具有自主知识产权的诊断产品和工具(二)中小型汽车零部件厂商开发汽车诊断产品的成本与效率和质量方面对某些中小型汽车零部件厂商而言,在开发具有诊断功能的车载ECU阶段后期,需对其进行测试,看所开发的ECU是否符合诊断协议,他们常用的测试方式是使用低成本的CAN网络测试工具,如周立功的 CANTEST软件,逐个手动输入所需要的基于诊断协议的诊断通信报文,来测试ECU的响应情况。另外,传统的简易CAN网络监测工具,只是对CAN报文进行显示,而无法对诊断协议内容进行解析,面对大量的通信报文通过人工肉眼进行逐字节解析以判断是否符合诊断协议,此种形式的开发工作显然不能休障开发的效率与质量。对中小型企业来说,若他们耗费几十万元购买国外诊断工具则成本太高。因此,对国内中小型汽车零部件厂商而言,研究低成本的基于IO15765国际诊断标准的诊断上位机工具,则可大大降低其产品开发成本,并确保产品开发的效率与质量。(三)基于CAN线的车载ECU在线下载的合理性与需求方面以往ECU在线升级大都是通过串口或BDM口进行程序下载,但针对于已装入汽车内通过CAN网络连接的ECU,无疑使用CAN总线对程序进行在线下载,会比较方便也是需求所在。在ISO15765-3中,对基于CAN总线的在线下载进行了统一、详细的实现约束,使车载网络ECU在线下载从整车网络规划与网络管理的角度进行统一规划。但由于IO15765在线下载技术的新颖性与技术本身的复杂性,目前在国内核心的学术研究期刊上尚未看到相关研究领域的报道,国内汽车厂商也尚未普遍使用此种方式对ECU进行程序的在线下载。因此,其下载工具未产业化,实际应用中符合要求的下载工具不多,或被作为大型工具的组件使用如( Canoe),但其成本较高并且灵活性较差。将程序下载通过CAN网络进行网络统一规划与管理,并使ECU通过CAN网络传输是在线下载的趋势所在,因此有必要研究基于ISO15765的CAN网络诊断的车载ECU程序在线下载技术。14论文主要研究工作根据上节所述的在车载CAN网络中诊断研究中所提出的问题,本文针对以上问题展开了相关的研究工作以及相关问题的解决。主要通过研究车载CAN网络国际标准ISO15765,对基于CAN网络的车载诊断进行研究、分析,设计基于ISO15765的车载CAN网络的上位机诊断。论文的主要研究工作的相互关系见图13,具体工作如下:重庆邮电大学硕士论文第一章绪论目标诊断网络结构分析ISO5765体系结构研究诊断需求分析搭建诊断测试平台,对诊断上位机进行测试常规诊断下载诊断常规诊断模模块设计模块设计块上位机实现低成利用VC与本上位机下载诊断模块上位机USBCANII图13论文主要研究工作的相互关系l通过深入研究基于车载CAN网络的国际诊断标准ISO15765的应用层与网络层协议,针对特定车载网终对象,设计车载网络诊断结构,并进行诊断需求分析2实现基于ISOl5765的诊断上位机的应用层与网络层协议。3设计基于SO15765的车载CAN网络诊断上位机。针对安全访问服务的实现过程,设计安全访问算法并建立安全算法动态链接库,利用VC软件平台与USBCANII硬件采集卡,设计车载CAN网络常规诊断模块的诊断上位机。4设计基于Iso15765的在线下载上位机。对下载诊断模块分别设计其预编程阶段与编程阶段,以及上位机对Sl9文件的解析处理。利用C软件平台及USBCANII硬件采集卡实现下载器上位机的设计。5根据诊断结构设计诊断测试平台,结合 CANoe与ISO15765诊断协议对所设计的诊断上位机进行测试。15本章小结本章首先介绍了课题研究背景与意义,然后概迟了车载网络诊断协议,重点分析比较了ISO14230与ISO15765协议,并分析基于CAN网络的ISO15765协议的优势。在此基础上分析并概述了因内车载CAN网络诊断存在并待解决的问题。最后提出了本文的研究工作。
- 2021-05-06下载
- 积分：1
