This　paper　studies　an　interval　data　min-max　regret　(IDMR)　version　of　the　packing-delivery　problem,　in　which　a　0-1　knapsack　problem　is　for　parcel　packing　and　a　capacitated　travelling　salesman　problem　is　for　parcel　delivery.　The　parcel　profits　for　the　courier　and　the　tour　costs　are　uncertain　and　they　can　take　any　value　from　a　specific　interval　with　lower　and　upper　bound　values.　The　problem　is　how　to　select　and　deliver　a　subset　of　parcels　to　minimise　the　maximum　regret　of　net　profit　which　is　the　difference　between　the　total　profits　of　the　selected　parcels　and　the　total　delivery　costs,　to　deal　with　the　trade-off　of　the　solution　robustness　and　performance.　To　tackle　the　problem　effectively,　we　first　prove　the　worst-case　scenario　of　a　solution　to　the　problem,　based　on　which,　a　mixed　integer　linear　programming　is　formulated.　A　Benders-like　decomposition　algorithm　is　then　developed　to　solve　small-scale　problems　to　optimality　within　the　manageable　computation　time.　For　medium-　and　large-scale　problems,　a　simulated-annealing-based　heuristic　method　with　a　local　search　procedure　is　designed.　Extensive　computational　experiments　show　the　efficiency　and　effectiveness　of　the　proposed　methods.