取货和送货问题算法帮助
我们假设为多家餐厅（比如 20 家）提供送餐服务。有（假设 10 个）可用驱动程序。此外，假设我们在 4 小时内收到 100 个订单，将食物从这些餐厅送到家庭。
因此，必须协调司机在某个地点取餐并将食物送到顾客家里。
主要目标是最大限度地缩短交货时间，即订购和到达家之间的时间。第二个目标是最大限度地提高司机的能力（即用最少的时间交付所有订单）。
请记住，订单的送达时间超过 4 小时，因此我们可以说均匀送达，即每 3 分钟送达一次。另外，我们假设 20 家餐厅的订单是随机的。
假设我可以精确到秒地计算从任何地点到目的地的旅行时间。
我实时知道所有司机的位置。我还知道他们的状态，即他们当前是否正在领取订单（前往已知目的地）的路上，他们是否已经领取订单并正在前往已知目的地的途中。
限制条件是： 1) 必须在指定时间（即餐厅备餐时间）后领取订单 2) 必须在 45 分钟内交付订单（否则将引发警报） 3) 必须用“x”分钟填充时间，以适应步行到商店取货订单等所花费的时间。 4) 必须用“y”分钟填充时间，以适应向客户交付订单和收取付款所花费的时间。 5) 司机只有一组给定的付款方式（例如现金、Visa、Amex、MasterCard）。我们必须将客户的要求（现金、签证等）与司机的能力（现金、签证、美国运通卡等）相匹配。
例如，如果我收到两个订单，目的地很近，取货地点也很近，即使有另一个“免费”司机（不做任何事情），使用同一个司机来取货和送货会更有效两个订单。
您可以假设每家餐厅都会强制执行送货区域，这意味着大多数从他们那里订购的人很可能都在他们附近。因此，该算法应该能够自动将驾驶员划分为城市区域，并优先考虑该区域内的驾驶员。
Let's assume food delivery for multiple restaurants (say 20). There are (say 10) drivers available. Further, let's say we get 100 orders over a 4 hour period to deliver food from these restaurants to homes.
So drivers have to be coordinated to pickup food at a location and deliver to customers at home.
Primary goal is to minimize time to delivery, i.e. time between order and arrival at homes. The secondary goal is to maximize driver capacity (i.e., least amount of time to deliver all orders).
Bear in mind that the orders come in over a four hour period, so let's say evenly, i.e. one very 3 minutes. Also, let's assume the orders are randomly to the 20 restaurants.
Assume that I can calculate time to travel from any location to a destination to the second.
I know the location of all drivers in realtime. I also know their statuses, i.e. are they currently on their way to pick up an order (to take to a known destination), have they already picked up an order and are enroute to a known destination.
Constraints are:
1) Must pick up an order after a given time (i.e. meal preparation time for restaurant)
2) Must deliver order in under 45 mins (otherwise alert thrown)
3) Must pad time with "x" minutes to accommodate for time spent walking to store to pickup order, etc.
4) Must pad time with "y" minutes to accommodate for time spent delivering order to customer and collecting payment.
5) Drivers have only a given set of payment methods (e.g. Cash, Visa, Amex, MasterCard). We must match customer request (cash, visa, etc) with driver capability (cash, visa, amex, etc).
So for example, if I get two orders with close by destination and close by pickup locations, even if there is another "Free" driver (not doing anything), it would be more efficient to use the same driver to pickup both orders and deliver both orders.
You can assume there will be delivery zones enforced for each restaurant, meaning, most people ordering from them will most likely be close to them. Therefore, this algorithm should manage to segment drivers automatically into city zones, and favor drivers within the zone already.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这听起来像是带有时间窗口的车辆路径问题的在线版本。我建议你谷歌一下并阅读出现的论文。
This sounds like an online version of the Vehicle Routing Problem with Time Windows. I suggest you Google that and read the papers that come up.
这取决于您为算法本身获得了多少开发时间（不包括 GUI、警报等）。
顺便说一句：如果你正在考虑暴力破解。不用担心：它不会扩展。
It depends on how much development time you got for the algorithm itself (not including GUI, alerts and all that).
BTW: if you're thinking about brute forcing it. Don't bother: it won't scale.