期刊名称：Relatórios de Pesquisa em Engenharia de Produção
电子版ISSN：1678-2399
出版年度：2010
卷号：10
出版社：Universidade Federal Fluminense (UFF)
摘要：The present work deals with the Vehicle Routing Problem with Si-multaneous Pickup and Delivery (VRPSPD). In this problem, the cus-tomers have both delivery and pickup demands. We propose undirectedand directed two-commodity .ow formulations, which are based on theone developed by Baldacci, Hadjiconstantinou and Mingozzi for the Ca-pacitated Vehicle Routing Problem. These new formulations are theo-retically compared with the one-commodity .ow formulation proposedby Dell'Amico, Righini and Salani. The three formulations were testedwithin a branch-and-cut scheme and their practical performance was mea-sured in well-known benchmark problems available in the literature. Theundirected two-commodity .ow formulation obtained consistently betterresults. We also ran the three formulations in a particular case of theVRPSPD, namely the Vehicle Routing Problem with Mixed Pickup andDelivery (VRPMPD). Several optimal solutions to open problems with upto 100 customers and new improved lower bounds for instances with upto 200 customers were found.
其他摘要：O presente trabalho trata do Problema de Roteamento de Ve′.culoscom Coleta e Entrega Simult.anea (PRVCES). Neste problema, os clientes possuem demanda tanto por entrega como por coleta. Prop.oem-se duasformula.c.oes em .uxo com duas comodidades, n.ao-orientada e orientada,baseadas na formula.c.ao proposta por Baldacci, Hadjiconstantinou e Min-gozzi para o Problema de Roteamento de Ve′.culos Capacitado. Estastr.es formula.c.oes s.ao teoricamente comparadas com a formula.c.ao em .uxocom uma comodidade proposta por Dell'Amico, Righini e Salani. Astr.es formula.c.oes foram testadas por meio de um procedimento branch-and-cut e seus desempenhos foram medidos atrav′es de problemas-testesdispon′.veis na literatura. A formula.c.ao em .uxo com duas comodidadesn.ao-orientada obteve consistentemente os melhores resultados. Tamb′emexecutou-se as tr.es formula.c.oes em um caso particular do PRVCES, par-ticularmente o Problema de Roteamento de Ve′.culos com Coleta e EntregaMista (PRVCEM). V′arias solu.c.oes ′otimas de problemas em aberto con-tendo at′e 100 clientes e novos limites inferiores de inst.ancias contendo at′e200 clientes foram encontrados.
关键词：Vehicle Routing with Simultaneous Pickup and Delivery;Commodity Flow Formulations; Branch-and-cut
其他关键词：Problema de Roteamento de Ve′.culos com Coleta eEntrega Simult.anea; Formula.c.oes em .uxo; Branch-and-cut
