随着社会经济和电子商务的快速发展,客户对货物的配送需求迅猛增加,门到门的快递配送服务占据越来越大的配送比例,使得负责快递运输的第三方物流公司面临很大的挑战,即如何在有限的时间内,合理地调度运输车辆,在满足客户需求的情况下,使得总运营成本最小,最后一公里的快递配送也成为亟待解决的问题。本文主要针对包含不确定因素的旅行商问题和车辆路径问题进行研究,具体如下：以电子商务环境为背景,对包含随机客户的旅行商问题进行研究。在电子商务环境下,客户每天上网购物存在一定概率,因此对快递配送服务的需求存在一定概率。如果一个快递公司为客户提供配送服务,其将获得一定收入并支付运输成本,为了使得获取的利润最大化,一些电商平台(比如中国著名电商平台一京东)建立自营物流,为部分客户提供物流配送服务,然后将一些偏远地区客户的配送服务外包给成本较低的第三方物流。在这种情况下,电商平台需要确定为哪些客户提供自营物流,并确定相应配送路径,然后将其余客户的配送服务外包给第三方物流。受启发于以上现实情况,提出新的路径优化问题——考虑利润的概率性旅行商问题(The Probabilistic Profitable Tour Problem, PPTP)。该问题假设所有客户具有相同的需求概率,目标为找出一条经过部分客户、期望利润最大的预优化路径,快递员按照预优化路径的顺序对存在实际需求的客户进行访问。文章构造了该问题的非线性规划模型,并设计了求解该模型的遗传算法。通过对几组较小和中等规模的例子进行求解,验证该算法的有效性。随后在PPTP的基础上,对客户需求概率不相同的情况进行研究,提出一类新的路径问题——同时考虑利润与随机客户的旅行商问题(Travelling Salesman Problems with Profits and Stochastic Customers, TSPPSC)。根据期望利润和期望成本的处理方式不同,TSPPSC可分为三个子问题：包含随机客户的选择性旅行商问题(Selective Travelling Salesman Problem with Stochastic Customers, STSPSC)、包含随机客户的奖励收集旅行商问题(Prize-collecting Travelling Salesman Problem with Stochastic Customers, PCTSPSC)以及同时考虑利润和随机客户的旅行商问题(Profitable Tour Problem with Stochastic Customers, PTPSC)。文章给出了这三个子问题的数学模型,然后设计了模拟退火混合遗传算法来对STSPSC问题进行求解,并通过一系列的实验来验证算法的有效性。实验结果表明本章所提算法能够很好的解决这一类新问题。针对旅行时间不确定的车辆路径问题进行研究。由于门到门的快递配送服务占据越来越大的配送比例,负责快递运输的第三方物流公司面临很大的挑战。与此同时,市区内配送车辆增多,使得城市的交通环境不断恶化。车辆配送过程中可能会遇到交通事故、车辆拥堵以及天气骤变等偶然因素,导致车辆行驶速度事先难以预料。例如：同一条道路,车辆在拥堵时刻的行驶时间可能是普通时刻的数倍,甚至数十倍。此时,物流公司的目标不仅仅为使得车辆的总行驶里程最短,而且希望在满足客户需求的情况下,使得车辆的总行驶时间最短。因此,本文放松车辆行驶速度为恒定的假设,假设车辆在道路上的行驶时间服从4个不同的速度函数,每个函数被选中的概率均为25%。这四种速度函数代表四种可能的道路状况。本章衡量运输车辆路线好坏的指标有四个,分别为车辆行驶总距离、车辆行驶总时间以及每辆车行驶距离和行驶时间的均衡度指标。由于涉及多目标优化,本文根据可行解中四个评价指标的关系,定义它们的支配关系,并设计自适应大规模邻域算法(Adaptive Large Neighborhood Search, ALNS)来寻找问题的Pareto非支配解集。ALNS嵌套在模拟退火算法的框架内,该算法的思想为通过使用移除算子和插入算子来不断的改进初始解,如果新产生的解比当前解要好,则用新产生的解作为下一次迭代的初始解。ALNS分别对单目标CVRP问题和多目标CVRP问题进行求解,通过将单目标CVRP问题的求解结果与标准遗传算法的求解结果和公布的最优解进行比对,验证算法的有效性。然后在四个指标值不同的权重组合下,对单目标CVRP问题的求解结果与多目标CVRP问题的求解结果进行比较分析。