2020年MathorCup高校数学建模挑战赛C题

12020年第十届MathorCup高校数学建模挑战赛题目C题仓内拣货优化问题某电商公司客户订单下达仓库后，商品开始下架出库，出库主要包含5个流程如下图所示：l定位：仓库有多个货架，每个货架有多个货格，商品摆放在货格中，且每个货格最多摆放一种商品，商品可以摆放在多个货格。订单下达仓库后，定位操作，确定商品下架的货格和每个货格下架的商品数量。l组单：单个客户订单商品数量少，对于中小件商品仓库，需要将多个客户的订单合并，构成任务单，这就是组单操作。l拣货：拣货开始，拣货员在某个复核台领拣货车及任务单，领取时间不计，然后根据推荐顺序依次访问任务单中商品所在货格，并下架商品，将商品放在拣货车上。下架完毕，拣货员将拣货车送往某个复核台，到达复核台后拣货员无需等待，继续领取拣货车和任务单，开始下一个任务单拣货流程。备注：(1)拣货员开始和结束复核台可以不一致。(2)一个拣货员负责对多个任务单时，每次只能拣一个任务单的商品。同一任务单，货格访问顺序不同，行走距离也有差异。(3)拣货员的行走速度为1.5m/s，商品下架过程，对任意一个货格，若下架商品数量小于3件，每件完成下架花费5秒，否则每件花费4秒。多人同时在一个货格拣货，不考虑等待的时间。l复核和打包：拣货时，拣货员可能多拣或者漏拣商品。拣货车放到定位组单拣货复核打包2复核台先对任务中商品复核，然后将商品按照订单打包。备注：(1)只有复核台正常工作时，才可以进行复核打包操作，每个订单复核和打包花费30秒。(2)只有拣货员将任务单中商品通过拣货车送到复核台后，复核台才能对该任务单中商品进行复核和打包。(3)若一个复核台完成该复核台所有任务单的复核和打包，没有新任务前，该复核台将处于空闲状态。从0时刻到TOTAL_TIME时刻，若一个复核台总空闲时间为IDLE_TIME，则该复核台利用率=1-IDLE_TIME/TOTAL_TIME。多人同时到达一个复核台时，需要考虑等待的时间。现有一个仓库，仓库数据见附件1“仓库数据.xlsx”，包括4个表格，前3个表格为仓库信息，包括货架、货格、复核台的位置及大小，货格和货架的关系。第4个表格为任务单信息，一个任务单包含多个订单，一个订单商品包含多个货格，一个货格需要拣多件商品。仓库示意图见图1，注意横纵坐标比例不是1:1。图1：仓库示意图（大图见附件2）3根据仓库数据附件1和附件2，仓库有13个复核台，4排货架，其中每排25组货架，每组2个货架，共50个货架，每个货架包含15个货格。水平方向每组货架之间的距离为1500毫米，竖直方向相邻两排货架纵向距离为2000毫米，货格长宽都是800毫米，复核台长宽都是1000毫米。备注：货架和复核台为障碍物，不可通行，其余位置均可通行。不用考虑拣货车尺寸，货架和复核台高度。图2：仓库左下角放大图（大图见附件2）说明：1.当绕障碍物折线行走时横向和竖向偏移都取d=750mm；2.复核台之间距离简化为两复核台坐标差的绝对值之和，如复核台A坐标，复核台B坐标，则两复核台距离为；3.货格与复核台距离简化为货格中点到复核台最近一条边中点的距离，如L1和L7）11(,)xy22(,)xy2121xxyy-+-4根据上述已知条件和要求，请完成以下问题：问题1：图2给出拣货员在仓内路线示例（L1-L7）。当拣货员在仓库中拣货时，需要在货格之间、货格与复核台之间、复核台与复核台之间行走。由于这些行走通常要绕过障碍物，不能直接采用坐标计算欧几里得距离。请你按照图中距离标示，设计一种计算3000个货格和13个复核台总共3013个元素之间距离的方法。（附件中货架坐标可理解为第一个货格左下角坐标，如S001的(x,y)表示货格S00101的坐标。其他相类似。复核台坐标也理解为左下角坐标。）问题2：假设所有复核台正常工作，任务单T0001等待拣货，拣货员P在复核台FH10领取了任务单T0001。请给P规划理想的拣货路线，包括货格访问顺序、返回的复核台，计算完成出库花费的时间（拣货员拣货开始到所有任务复核打包完成花费的时间）。问题3：假设2个复核台(FH03，FH11)正常工作，5个任务单（T0002-T0006）等待拣货，继续由拣货员P负责拣货，P初始位置为FH03。通过建模和优化，请给P指定任务领取顺序，规划理想的拣货路线，使得这些任务尽快出库。请计算完成出库需要花费的时间和每个复核台利用率。问题4：假设4个复核台（FH01，FH03，FH10，FH12）正常工作，49个任务单（T0001-T0049）等待拣货，9个拣货员（P1-P9）负责拣货，请给每个拣货员分配任务单、起始拣货复核台，并分别规划理想的拣货路线，使得49个任务单尽快完成出库，并计算完成出库需要花费的时间和每个复核台利用率。5问题5：在问题4中，有4个复核台（FH01，FH03，FH10，FH12）正常工作，请评估增加一个正常工作的复核台对出库时间的影响。问题6：商品在货架中的摆放位置，会影响拣货效率。若将畅销品放置在离复核台较近的位置，拣货员行走距离相应减少，但畅销品所在货架可能拥挤，反而降低拣货效率。对于仓内商品摆放问题，你有什么建议？注：在问题3，4，5中，当一个人有多个任务时，只能一个一个任务完成，不能在完成一个任务过程中拣另一个任务的货。附件4计算结果文件要求说明：为验证计算结果，本赛题需要提交数据文件文件名为：C队号计算结果.xlsx。问题1数据填入Ques1中，给出3013个元素的最短距离矩阵3013﹡3013。序号顺序为S00101，S00102，…，S00115，S00201，…，S20001，S20002，…，S20015。复核台FH01，FH02，FH03，…，FH13。也即S00101标号为1，S00102标号为2，…，S20015标号为3000，复核台FH011标号为3001,复核台FH02标号为3002，…，FH13标号为3013。将得到的最短路矩阵填入表单Ques1。该最短路矩阵共占3013行和3013列。行从1行开始，列从A列开始。6问题2数据填入Ques2。第2列原始名称中3—25行为任务1中的23个商品货格号；第3列为复核台或商品货格对应的标号，范围为1—3013。第4列为对应商品货格的件数，在附件仓库数据任务单中商品件数列中直接摘抄即可。复核台商品件数标0即可。问题3数据填入Ques3与问题2表单意义相同。只是增加了一列任务单。注意当完成一个任务后，回到一个复核台，下一次即从该复核台领取任务单出发。问题4数据填入Ques4与问题3表单意义相同。只是增加了一列人（P1-P9）。