如今,凭借着电子设备和网络技术的电子商务作为我国当下新的商业运作模式,正在迅速渗透到每一个行业领域。电子商务不仅提供了购物的便利性,同时也提供了如配送等优质的附加服务,为物流行业的发展推波助澜。它的商业优势日渐凸显,市场交易份额不断地扩大,展现出电子商务强大的发展潜力和无法匹敌的行业竞争力。对企业而言,提供物流配送路径短、成本低、速度快的物流配送服务,不仅使得顾客更快的收到自己购买的商品,提高顾客满意度和忠诚度,同时还能增强企业的竞争力。因此,降低整个物流行业的成本已经成为当今电商企业为提供高效、精准、敏捷的物流配送服务的主要目标。在信息科学技术应用不断扩大的背景下,消费者消费观念的转变伴随着电商行业的交易规模日益增长。尤其在促销节日期间,电商物流配送量和配送规模的激增,给电商企业带来了巨大的配送压力。对A企业来讲,如何合理安排多种车型车辆共同配送的路径,降低总体配送成本、提高企业的经济效益和服务水平等问题一直都有待解决。已知A企业客户数量众多,配送规模较大,直接为客户提供配送服务相对来讲比较困难。本文在分析了A企业物流现状问题后,将A企业的配送问题简化为带软时间窗的多车型路径问题,采用“先聚类,后排程”的思想解决复杂的配送问题。首先,基于网格划分的方法将客户分布的地理位置映射到子单元格中进行划分;然后,根据改进的最大最小距离算法对客户进行初步聚类;最后,针对划分后的客户群体的配送问题建立带软时间窗的单车型TSP模型,并利用MATLAB调用Cplex软件进行求解,解出每个类别所包括客户的配送路线图及配送成本。针对Cplex求解问题的适用条件,在调用Cplex求解的过程中,对本文中遇到的软时间窗和租赁成本等整数非线性规划问题的特点,提出将软时间窗约束线性转化的方法,并解决在Cplex中软时间窗的求解困难问题。在求解过程中发现,车辆开始配送的服务时间和配送总成本之间有着密切的关系,因此,对二者进行了灵敏度分析,进而找到了一个适合A公司的配送方案。本文采用“先聚类,后排程”的思想,设计了基于网格划分的最大最小距离的聚类算法,通过对算例的求解和结果分析验证了该算法不仅可以有效的降解问题的求解复杂程度,同时也验证了Yalmip工具箱在求解整数规划模型的有效性,对解决带时间窗的多车型VRP问题提供了一种可具参考性的解决方案。