配送是物流系统中非常重要的一个环节,在物流的各项成本中,配送成本占了相当高的比例,降低物流配送成本成为物流管理过程中首要考虑的问题之一。配送线路合理与否对配送速度、成本、效益影响很大,因此,配送中的核心问题—车辆路径问题(简记VRP)吸引了企业决策者和理论研究者们的普遍关注。带软时间窗的车辆路径问题(简记VRPSTW)是经典VRP的一个重要扩展分类,是在车辆路径问题的基础上添加时间窗约束,并且希望供应商尽可能在时间窗内为客户提供服务,如果供应商的服务时间超出时间窗一定限度,客户也能够接受服务,但对供应商有一定的惩罚。在高度发展的商业社会中,消费者对时间的要求越来越严格,特别是随着Internet的普及,电子商务以及其他信息技术和信息服务的研究和发展,这使得研究VRPSTW有重要的现实意义和理论价值。本文是以VRPSTW为研究对象,主要工作分为四部分:第一部分详细阐述了VRP的特点、分类,以及VRP的国内外研究现状,然后再结合午餐配送实际提出本文要研究的VRPSTW。第二部分详细介绍了遗传算法的基本概念,基本原理及流程,为本文算法的设计打下了理论基础。虽然标准遗传算法可以实现均衡的搜索,但并不保证全局最优收敛,本文对遗传算法做了改进,以保证算法的全局优化能力和收敛能力。第三部分通过对VRPSTW建立数学模型,进一步明确了问题的目标函数和约束条件。本文求解VRPSTW的过程是先用算法软件lingo8.0计算整数规划模型,初步确定派车方案,即需要调用的车辆数和车辆型号。然后根据车辆数和车辆容量约束,结合遗传算法,编译相应的C语言程序软件,求得最优解。根据运算结果,确定各车辆的行驶路线,安排各车辆的服务对象和停靠顺序。第四部分以安徽蚌埠味多多营养午餐配送公司为实例,分析了该公司亟待解决的问题,根据本文设计的算法提出相应的解决方案。