基于NCL的同城配送车辆取送货物路径优化韩子龙，李向文**510152025303540（大连海事大学交通运输管理学院，大连116026）摘要：为了降低同城配送企业的物流配送成本，采用配送车辆动态穿梭取送货物的新模式，将配送车辆取送货物行走的距离转化为距离窗口，以多配送车辆取送货物行走距离之和最小化为目标函数，应用自然约束语言NCL建立了配送车辆取送货物路径优化的数学模型，设计了相应的NCL求解规则。考虑到问题的NP性，结合实例，利用基于NCL的POEM物流优化平台软件进行优化求解，实例验证了POEM求解的高效性，并得出了最优配送路径。关键词：物流；距离窗口；NCL；优化中图分类号：U121ThePathOptimizationofIntra-cityVehicleTakinggoodsandDeliveringBasedontheNaturalConstraintLanguageHANZilong,LIXiangwen(TransportationManagementschool,DalianMaritimeUniversity,Dalian116026)Abstract:ForthesakeofreducingthecostofLogisticsCompany,dynamicshuttletopickupgoodsanddelivergoodsispresented.Thedistanceofvehicleistransformedintodistancewindow.ThemodebasedontheNaturalConstraintLanguageispresentedwithminimizingthevehicledeliverydistanceastheobjectivefunctionandtheNCLsolvingrulesaredesigned.BecauseoftheNPproblem,theoptimizelogisticsplatformsoftwarecalledPOEMisusedtosolvethegivenexampleTheefficiencyofPOEMisverifiedandtheoptimaldistributionpathisgivenatlast.Keywords:logistics;distancewindow;NaturalConstraintLanguage;optimization0引言简要随着我国经济社会发展水平的不断提高，我国配送企业也处在迅速发展的时期。同城配送业务作为物流业务的一个分支，是指在同一个城市区域内进行货物的配送业务。它强调为客户提供迅速、准确、周到、优质、高效的个性化服务，其主要的面向客户为同城内的工商企业和个人客户。该板块竞争激烈，同城配送市场扩张迅速，发展潜力巨大。但与此同时，配送企业也面临着诸如如何降低运送成本，如何节约运送时间等关系到公司利益的一系列问题[1]。在传统的同城配送模式下，配送企业以收发站为中心派车上门收取配送货物，然后将收集到的货物统一运送到配送中心，最后,在配送中心进行相关统计处理后，再派车将货物配送到客户手中。在这样一种模式下，配送企业势必要承担多点派车揽收快件的费用而增加了公司的开支[2-3]。为了解决这一问题，采用配送车辆动态穿梭同时取送货物的新模式，减少由于多点派车揽收快件而产生的费用。国外学者对于同时取送货物的研究比较多，像VanderBruggen，IrinaGribkovskaia，KGanesh等都对该问题做过相应的研究[4-7]，近年来，国内学者也在该问题上做了一定的研究，作者简介：韩子龙（1989-），男，硕士研究生，主要研究方向：物流信息化与物流系统优化通信联系人：李向文（1956-），男，副教授，主要研究方向：物流信息化.E-mail:xawenli@163.com-1-易荣贵等[8]采用遗传算法对路径优化问题进行求解，蓝伯雄等[9]提出了一种概率式禁忌搜索算法对取送货问题进行求解,段凤华等[10]利用禁忌搜素算法对相关问题进行了研究。由于同时取送货物问题是NP问题，在以往对该问题的研究上，学者建立相关数学模型后，往往通4550过设计相应的启发式算法进行求解，文章依托自然约束语言，用常规数理逻辑对该问题进行建模描述，通过设计相应的求解规则，利用POEM物流优化平台对所建模型进行实例的模拟仿真，达到了高效的求解效率。1自然约束语言的简介自然约束语言，即NCL（NaturalConstraintLanguage），是一门以标准的数理逻辑为语法的描述型语言。在这一意义上，NCL是新一代的语言，与传统声明型语言及脚本型建模语言不同，NCL是第一个采用上下文相关语法的、用于求解约束满足问题的描述型语言。因而NCL支持对变量类型的隐式声明，可根据上下文约束进行推理及求解。NCL也是一门集逻辑、优化及求解规则为一体的智能描述型语言，它支持业务建模和问题求解，是POEM优化平台的基础和核心[11]。其求解机制见图1所示。55图1NCL求解机制Fig.1NCLsolvingmechanism2问题描述及NCL语言建模602.1问题描述...